この問題はサンプル試験に関するもので、私たちの教授は怠惰すぎて解答を入力できず、私はかなり行き詰っています。よろしくお願いします。
次の言語が文脈自由であることを証明してください{x is an element of {a,b,c}* | the number of a's in x is greater than the number of b's or the number of c's in x}
この問題はサンプル試験に関するもので、私たちの教授は怠惰すぎて解答を入力できず、私はかなり行き詰っています。よろしくお願いします。
次の言語が文脈自由であることを証明してください{x is an element of {a,b,c}* | the number of a's in x is greater than the number of b's or the number of c's in x}
{xは{a、b、c}の要素です* | xのaの数がxのbの数またはcの数よりも大きい}
これは2つの方法で解釈できます。
a
)より大きいb
c
a
'sの数よりも大きいb
)または('sの数がa
'sの数よりも大きいc
)。1のヒント:PDAは次のように機能します。スタックが空a
で、入力にが表示されている場合は、スタックにを追加a
します。スタックが空で、入力にab
またはaが表示されている場合は、スタックc
にaを追加b
します。最上位のスタックシンボルがaで、入力にb
が表示a
されている場合は、スタックからaを削除しb
ます。最上位のスタックシンボルがaで、入力にb
ab
またはaが表示されている場合は、スタックc
に別のシンボルを追加b
します。最上位のスタックシンボルがで、入力にa
が表示a
されている場合は、スタックに別のシンボルを追加a
します。最上位のスタックシンボルがで、入力にまたはがa
表示されている場合は、b
c
a
スタックから。ここで、そのようなPDAは(1)'sの数が'sと'sのa
数の合計に等しい場合、空のスタックを持つという引数を単純に作成します。(2)スタックの一番上にあるのは、 'sまたは's(組み合わせたもの)よりも多くの'sを見た場合です。(3)'sまたは's(組み合わせ)のいずれかよりも'sが少ない場合は、スタックの一番上にあります。b
c
a
a
b
c
b
a
b
c
a
ヒント2:まず、 's、b
' s、およびc
'sの任意の文字列を受け入れるPDAを作成し、a
' b
sを無視しますc
(上記のヒント1のPDAは、無視するように簡単に変更できますc
の)。a
次に、「s」 、b
「s」、および「s」の文字列を受け入れるPDAを作成します。この文字列は、「s 」よりもc
多く、「 」を無視します(作成したものと同様)。最後に、文脈自由を証明しようとしている言語が、これらのオートマトンによって受け入れられる言語の結合であることを示します。簡単な議論で十分です。文脈自由言語は和集合の下で閉じられているので、これは主張を示しています。つまり、文脈自由を証明するために設定した言語は、a
c
b
さらに詳しい説明をお気軽にリクエストしてください。また、次のような質問については、新しいサイトをチェックしてください:https ://cs.stackexchange.com/ 。あなたはそのサイトで将来の質問についてさらに良い答えを受け取るかもしれません。
タスクは、言語が文脈自由文法によって生成できることを示すことです。
いくつかのヒント:
A -> aabAc | B
B -> B|epsilon