compiler-construction - CFG 文法定義

Question

言語を生成する CFG (コンテキストフリー言語) を定義します。

L={a^nb^mc^n | n,m>=0}

誰でも問題に対処する方法を教えてもらえますか?

私の理解では、L は次のような要素で構成されています: { aabbbcc } (n=2 および m=3 と仮定しました)

前もってありがとうヨアヒム

score 2 · Accepted Answer

これは宿題のように聞こえるので、いくつかのヒントを示します。

文脈自由文法で a と c の数を一致させるにはどうすればよいでしょうか?

b のシーケンスを生成するには、どのような種類のプロダクションを使用できますか?

これら 2 つの部分問題を組み合わせて、単一の文脈自由文法にするにはどうすればよいでしょうか?

score 0 · Accepted Answer

言語を生成する文脈自由文法を考える

L1 = {a^nc^n : n >= 0}

そのような

G1 = <{S},{a,c},S,{S -> aSc,S-> λ}>

の派生はG1、次のように特徴付けることができます。

G1 =>1 S        (via S)
   =>* a^nSc^n  (via n >= 0 applications of S -> aSc)
   =>1 a^nc^n   (via S -> λ)

文法は、言語における「」と「」のG1数と配置の間に必要な関係を確立し、規則の適用で終了します。acL1S -> λ

G1ルールを適用しての導出を終了する方法と、空の文字列の代わりにS -> λ一連のを生成する方法を検討してください。m >= 0 bこれは、もう少し一般的な問題の解決策です。L2文法によって生成された言語があるとします

G2 = <V,N,S2,P>

L2同数のとで囲まれたa文字列を生成するにはc、の規則をG1次のように拡張して文法を取得しますG1'。

G1' = <{S} ∪ V,{a,c} ∪ N,S,{S -> aSc,S -> S2} ∪ {P}>

問題を解決するには、それを生成するL2言語{b}*とG2通常の文法を考えてみましょう。

2 に答える 2