計算コースのモデルで得た 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 * の下で閉じられます...誰かがこれを帰納的な形式に形式化するのを手伝ってくれれば、私はそれを感謝します。
ありがとう