0

この問題はサンプル試験に関するもので、私たちの教授は怠惰すぎて解答を入力できず、私はかなり行き詰っています。よろしくお願いします。

次の言語が文脈自由であることを証明してください{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}

4

2 に答える 2

1

{xは{a、b、c}の要素です* | xのaの数がxのbの数またはcの数よりも大きい}

これは2つの方法で解釈できます。

  1. 'の数が('の数に'の数を加えたものa)より大きいbc
  2. ('sの数がa'sの数よりも大きいb)または('sの数がa'sの数よりも大きいc)。

1のヒント:PDAは次のように機能します。スタックが空aで、入力にが表示されている場合は、スタックにを追加aします。スタックが空で、入力にabまたはaが表示されている場合は、スタックcにaを追加bします。最上位のスタックシンボルがaで、入力にbが表示aされている場合は、スタックからaを削除しbます。最上位のスタックシンボルがaで、入力にbabまたはaが表示されている場合は、スタックcに別のシンボルを追加bします。最上位のスタックシンボルがで、入力にaが表示aされている場合は、スタックに別のシンボルを追加aします。最上位のスタックシンボルがで、入力にまたはがa表示されている場合は、bcaスタックから。ここで、そのようなPDAは(1)'sの数が'sと'sのa数の合計に等しい場合、空のスタックを持つという引数を単純に作成します。(2)スタックの一番上にあるのは、 'sまたは's(組み合わせたもの)よりも多くの'sを見た場合です。(3)'sまたは's(組み合わせ)のいずれかよりも'sが少ない場合は、スタックの一番上にあります。bcaabcbabc

aヒント2:まず、 's、b' s、およびc'sの任意の文字列を受け入れるPDAを作成し、a' bsを無視しますc(上記のヒント1のPDAは、無視するように簡単に変更できますcの)。a次に、「s」 、b「s」、および「s」の文字列を受け入れるPDAを作成します。この文字列は、「s 」よりもc多く、「 」を無視します(作成したものと同様)。最後に、文脈自由を証明しようとしている言語が、これらのオートマトンによって受け入れられる言語の結合であることを示します。簡単な議論で十分です。文脈自由言語は和集合の下で閉じられているので、これは主張を示しています。つまり、文脈自由を証明するために設定した言語は、acb

さらに詳しい説明をお気軽にリクエストしてください。また、次のような質問については、新しいサイトをチェックしてください:https ://cs.stackexchange.com/ 。あなたはそのサイトで将来の質問についてさらに良い答えを受け取るかもしれません。

于 2012-04-05T13:47:57.323 に答える
-2

タスクは、言語が文脈自由文法によって生成できることを示すことです。

いくつかのヒント:

A -> aabAc | B
B -> B|epsilon
于 2012-04-05T00:45:47.747 に答える