「(」「)」と「;」の 3 つの記号があるとします。
次の基準を満たす S 式の文脈自由文法の生成規則を作成するにはどうすればよいですか?
- 式全体が括弧で囲まれています。つまり、"(" で始まり ")" で終わります。
式が左から右に読み取られる場合、式の任意の位置 (最後のものを除く) にある開き括弧の量は、閉じ括弧の量よりも大きくなります。式の最後では、開き括弧の数と閉じ括弧の数が等しくなければなりません。
- ブラケットは、どのような方法でも入れ子にすることができます。
- 閉じ括弧と開き括弧は「;」で区切る必要があります。
- 最も内側の括弧には「;」を含めることができます または空のまま。
- ";" 連続して発生してはなりません。
また、導入された非終端文字には大文字を使用する必要があります。
文法に含まれる文字列:
()
(;)
(((;)))
((;);((;)))
(();(()))
文法に含まれていない文字列。
;
(;;)
(()())
());(()
();()
;()
ε
次の文法を使用してみましたが、間違った値が得られます。入力/修正を歓迎します。
S --> (BAB)
A --> ; | ε | (A)
B --> B | A | A);(A