grammar - この言語の文法を見つける

Question

次の言語の文脈自由文法を見つける必要があります。

L= { w from { a,b,c,d }* : #a+2#b=2#c+#d }

これが私の試みですが、それが正しいとは思えません：

S -> aSd|dSa|BSC|CSB|abSdc|baScd|dcSab|cdSba|SS|λ
B -> c|dd
C -> b|aa 

Answer 1

次のように、言語を認識する PDA を作成できます。

• 入力の文字aとbは、スタックに対応しaます。
• 文字cとはスタック上でd対応しcます。
• スタックが空であるか、トップがaでありa、入力にある場合は、それを消費してスタックにプッシュaします。
• スタックが空であるか、トップがaでありb、入力にある場合は、それを消費してスタックにプッシュaaします。
• スタックが空であるか、トップがcでありc、入力にある場合は、それを消費してスタックにプッシュccします。
• スタックが空であるか、トップがcでありd、入力にある場合は、それを消費してスタックにプッシュcします。
• スタックトップが入力上にある場合はc、aを消費aしてポップしcます。
• スタックトップが入力上にある場合はc、bを消費bしてポップし、スタックが空の場合は別のものをポップするか、 をプッシュするc特別な状態に移動します。ca
• ...
• 受け入れ状態は、入力とスタックの両方が空の状態です。

つまり、CFG を構築できる必要があります。あなたは正しい方向に進んでいると思いますが、順序の制約がないため、この CFG を書くのは大変です。これは、同じ基本ルールの順列がたくさんあることを意味します。