次の正規表現があります: ((abc)+d)|(ef*g?)
ここで見ることができるDFAを作成しました（正しいことを願っています）
タスクは通常の文法 (チョムスキー階層タイプ 3) を作成することですが、わかりません。しかし、私は次のような通常の文法を作成しました。
S→aT
T→b
T→c
T → dS
S → eT
S→eS
T → ε
T→f
T → fS
T → gS
よろしくパトリック
1 に答える
0
タイプ 3 チョムスキーは、次の規則の使用に制限された通常の文法のクラスです。
X -> aY
X -> a,
ここで、X は任意の非終端記号と任意の終端記号です。規則は、右辺のいずれにも存在しないA -> eps場合にのみ許可されます。A
工事
正規表現が (abc)+d または ef*g? の 2 つの可能性で構成されていることがわかります。したがって、最初のルールはS -> aTandになりS -> ePます。これらのルールにより、2 つの可能性のいずれかの作成を開始できます。非終端記号は必然的に異なることに注意してください。これらは、対応するオートマトンの完全に異なる分離パスです。次に、両方の正規表現を別々に続けます。
(abc)+ 少なくとも 1 つのシーケンス abc の後に 0 回以上のオカレンスが続きます。これを次のようにモデル化できることは容易にわかります。
S -> aT
T -> bU
U -> cV
V -> aT # repeat pattern
V -> d # finish word
ef*g? ここでは、e の後に 0 個以上の f 文字とオプションの g が続きます。最初の文字が既にあるため (最初の 2 つのルールのいずれかで指定されています)、次のように続けます。
S -> eP
S -> e # from the starting state we can simply add an 'e' and be done with it,
# this is an accepted word!
P -> fP # keep adding f chars to the word
P -> f # add f and stop, if optional g doesn't occur
P -> g # stop and add a 'g'
結論
これらを組み合わせると、言語の文法が形成されます。あなたがそれを理解できるように、私は思考の流れを書き留めようとしました。
演習として、次の正規表現を試してください: (a+b*)?bc(a|b|c)*
于 2015-01-14T18:01:04.787 に答える