次の言語が文脈自由であることを証明してください：

Question

この質問は、私たちの教授が解決策をタイプするにはあまりにも怠っていて、かなり悪いです。あなたの助けを前もってありがとう！

は以下の言語は文脈自由であることを証明 {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}

Answer 1

{xは{B、C} *の要素であります|

1. a年代の数がより大きい（：xの者の数は、Bの数やこれには2つの方法で解釈することができ、XのCさん}

の数よりも大きいですbの数年代プラスcの数年代）

（aの数S「sはbの数よりも多い」の）または（aの数 『sはcの数よりも大きいです』 s）。

ヒント1：PDAは次のように動作します。スタックが空で、入力にaがある場合は、aをスタックに追加します。スタックが空で、入力にbまたはcが表示されている場合は、bをスタックに追加します。一番上のスタックシンボルがbで、入力にaが表示されている場合は、スタックからbを削除します。一番上のスタックシンボルがbで、入力にbまたはcが表示されている場合は、bをスタックに追加します。一番上のスタックシンボルがaで、入力にaが表示されている場合は、aをスタックに追加します。一番上のスタックシンボルがaで、入力にbまたはcが表示されている場合は、スタックからaを削除します。今度は、そのようなPDAがaの数がbの数とcの数の合計に等しい場合、（1）空のスタックを持つ引数を生成してください。 （2）aがスタックの最上部にある場合は、は、bまたはcのいずれかを見たよりも、aのほうが見えます。 （bまたはcのいずれかを見たよりも、aのほうが少なかった場合は、スタックの最上部にあるb）。 2

ヒント：まず、S 'の任意cを無視して、S' のbよりS 'のよりaを有するS' のa年代、b年代、及びcの任意の文字列を受け付けるPDAを構築（PDAは、上記1のヒントではcのものを無視するように簡単に変更できます）。そして、aの文字列、bの文字列、cの文字列を受け入れるPDAを構築してください。これは、bのものを無視して、よりもaのほうです。最後に、文脈自由を証明しようとしている言語がこれらのオートマトンによって受け入れられた言語の和集合であることを実証してください。簡単な議論で十分です。文脈自由言語は組合によって閉鎖されているので、文脈自由であることを証明するために設定した言語は文脈自由であるという主張を実証している。

さらに詳しい説明をリクエストしてください。また、新しいサイトでhttps://cs.stackexchange.com/のような質問をチェックしてください。そのサイトの今後の質問については、より良い回答が得られるかもしれません。

Answer 2

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

ヒント：

A -> aabAc | B 
B -> B|epsilon