1

計算コースのモデルで得た HW に関するいくつかの質問についてサポートが必要です。テキストの関連する章 (Michael Sipser の計算理論入門) を読みましたが、これらのハードウェアに関する質問には、この本では得られなかった知識が必要であると感じています... 最初の質問は次のとおりです。

(1) L* = {a}* {b}* となるような言語 L が存在しないことを証明せよ。

明らかに右側は正規表現です。0 個以上の a の後に 0 個以上の b が続きます。これは、空の文字列イプシロンの場合もあります。

問題は L* で発生します。言語に適用された * が何をするのか、または言語 L の * のためにこの方程式をどのように処理するのか、まったくわかりません。

この質問に対するヘルプまたはリソースをいただければ幸いです。

=====

2番目の質問は簡単で、ほとんどできる気がします。私はそれを自分自身に正当化できるので、問題はそれを正式に書くことだと思います。2番目の質問はこれです：

(2) A と V が同じアルファベット (シグマ) の言語であり、A (が B の部分集合) である場合、A* (は B* の部分集合) であることを証明してください。ヒントは、誘導を使用することです。

明らかに (たとえば) sigma = {1, 0} の場合

および A = {00, 01, 10, 11}

B = {00, 01, 10, 11, 100, 101, 110, 111}

次に、B = A + 他のものがあるため、A * 内のすべてが B * の下で閉じられます...誰かがこれを帰納的な形式に形式化するのを手伝ってくれれば、私はそれを感謝します。

ありがとう

4

1 に答える 1

1

(1) の便利な再帰的定義は次のL*とおりです。

  1. イプシロンが入っていますL*
  2. ある場合、xあるLxL*
  3. xとyが にある場合L*、そうですxy
  4. L*は、1. - 3. を満たす最小の言語です。L

この定義を考えると、矛盾による証明は次のとおりR* = a*b*です。それからabですR*。3.までに、ababも入っている必要がありますR*。しかしR* != a*b*、矛盾。したがってR* = a*b*、偽でなければなりません。言い換えれば、どの言語Rも ではありませんR* = a*b*。

直感は非常に簡単です:L*は、 から 0 個以上の文字列 (繰り返しは許可されています) を連結することによって形成できるすべての文字列の言語ですL。再帰的な定義は、ゼロの文字列 (1.)、1 つの文字列を厳密に取得する文字列L(2.)、潜在的に多くの文字列を結合して形成される文字列L(3.) を許可することで機能します。

(2) 上記の定義を使用して、 の連結された文字列の数を帰納的に進めますA*。連結が 0 の場合、空の文字列は と の両方A*にB*あるため、問題ありません (ルール 1 を参照)。1 つの連結の場合、Aは のサブセットであるBため、 の文字列はに含まAれA*(ルール 2 を参照)、stringsfromBは に含まれるためB*(同じルール)、1 つの連結を含むすべての文字列A*も に含まれB*ます。ここで、 でk連結されるすべての文字列A*も にあると仮定しB*ます。k+1で連結された文字列はA*どうですか? これらはルール 3. を使用して形成さxれyますA*。k+1連結、つまり、多くてもk連結です。言い換えると、連結をA*取る文字列は、 whereとare in 、 andとk+1書き換えることができ、多くても連結できます。最大で連結されたすべての文字列も含まれているため(私たちの仮説によると)、それがあり、B* に含まれています。ルール 3. により、も含まれている必要があります。したがって、連結された文字列も に属している必要があります。これで証明が完了する.xyxyA*xykA*kB*xyxyB*k+1A*B*

注: これはいくつかの詳細を省略しており、あまり形式的ではありませんが、アイデアを理解して形にすることができれば幸いです。これより洗練されたものが必要な場合はお知らせください。

于 2012-06-25T23:32:16.860 に答える