1

このための文脈自由文法の開発に関連する思考プロセスを誰か教えてもらえますか? 特定の数の 0 と特定の数の 1 がある言語を与えられましたが、0 の数は 1 の数と等しくありません。ただし、0 が最初に来てから 1 が来ます (これにより、物事がより簡単になります)。したがって、受け入れ可能な文字列は 0000111 または 01111111 です。

私はあなたに直接的な答えを教えてほしくありません。それを理解するプロセスだけです。

4

1 に答える 1

3

さて、あなたが望まない直接的な答えは次のとおりです。

S - initial symbol
S -> X | Y
X -> 0X1 | X1 | 1
Y -> 0Y1 | 0Y | 0 

最初に頭に浮かぶことなので、プロセスはそれほど多くありません。とにかく、最初に確認しなければならないことは、2 つの可能性があるということです。1 が多いか、0 があり、問題を 2 つに分割するのが良いでしょう (S を X と Y に分割したように)。

次に、「コンテキストフリー」では、0 と 1 の境界以外の場所で数値を制御できないことがわかります。アイデアを得て、解決策を書き留めるだけです。

于 2013-10-09T19:38:52.273 に答える