9

一部の正規言語を同等の文脈自由文法に変換するにはどうすればよいですか? その正規表現に対応する DFA を構築する必要がありますか、またはそのような変換のための規則はありますか?

たとえば、次の正規表現を考えてみましょう

01+10(11) *

上記の正規表現に対応する文法はどのように記述できますか?

4

3 に答える 3

15

  • A+B を文法に変更

    G -> A
G -> B

  • A* を

    G -> (empty)
G -> A G

  • ABをに変更

    G -> AB

A と B を再帰的に処理します。ベース ケースは空の言語 (生成なし) と単一の記号です。

あなたの場合

 A -> 01
 A -> 10B
 B -> (empty)
 B -> 11B

言語が有限オートマトンで記述されている場合:

  • 状態を非終端記号として使用する
  • 言語を端末記号のセットとして使用する
  • 元のオートマトンの文字 a の任意の遷移 p -> q に遷移 p -> aq を追加します
  • 文法で初期状態を初期記号として使用する
于 2010-04-14T17:31:56.657 に答える
6

V->w の形式の規則を使用して形式的な文法に変換することを意味していると思います。ここで、V は非終端記号であり、w は終端記号/非終端記号の文字列です。まず、次のように言うだけです (CFG と正規表現の構文を混ぜて):

S -> 01+10(11)*

ここで、S は開始記号です。少し分解してみましょう (わかりやすくするために空白を追加します)。

S -> 0 A 1 0 B
A -> 1+
B -> (11)*

*重要なのは、 es と+es を再帰に変換することです。まず、空の文字列を受け入れる中間ルールを挿入して、Kleene スターをプラスに変換します。

S -> 0 A 1 0 B
A -> 1+
B -> (empty)
B -> C
C -> (11)+

+最後に、表記を再帰に変換します。

S -> 0 A 1 0 B
A -> 1
A -> A 1
B -> (empty)
B -> C
C -> 11
C -> C 11

を処理するx?には、空を生成するルールと x を生成するルールに単純に分割します。

于 2010-04-14T17:27:22.000 に答える
2

実際、異なる CFG 文法で同じ言語を生成できます。そのため、正規表現 (正規言語) が与えられた場合、その CFG へのマッピングは一意ではありません。

確かに、特定の正規表現になる CFG を作成できます。上記の回答は、これを達成するためのいくつかの方法を示しています。

これにより、高レベルのアイデアが得られることを願っています。

于 2012-05-15T20:03:53.740 に答える