context-free-grammar - これは自由文脈文法言語ですか?

Question

これは文脈自由言語ですか？

{a^(2k) b^n c^n : k >= 0 ∧ 0 <= n <= m}∪<br> {a^(2k+1) b^n c^m :k >= 0 ∧ n >= m >= 0}

Answer 1

言語が文脈自由言語であることを証明する 1 つの方法は、指定された言語の文脈自由文法を作成することです (または PDA を描画します)。

以下の言語:

{a ^(2k) b ⁿ c ^m : k >= 0 および 0 <= n <= m} U {a ^(2k+1) b ⁿ c ^m : k >= 0 および n >= m >= 0}

文脈自由言語です

_{私があなたの質問にコメントしたように、あなたは質問の書き方を間違えたと思います、私は上記の文法のためにやっています}

この言語の Context-Free-Grammar を書くことができます:

が単一の変数 α --> βである種類の文脈自由文法生成において。α

S --> S ₁ | S2 _{_}

S ₁はこの部分 {a ^(2k) b ⁿ c ^m : k >= 0 and 0 <= n <= m} を生成し、S ₂ は {a ^(2k+1) b ⁿ c ^m : k >= 0 and n を生成します>= m >= 0}

S ₁ --> AB

あ --> ああ | ^

B --> bBc | ^

B --> Bc

と

S ₂ --> AaC

C --> bCc | ^

C --> bC

文法Sでは start Variable と {S, S ₁ , S ₂ , A, B, C} はすべて variable です。
したがって、上記の文法では、すべてのプロダクションは が単一の変数 の形式α --> βであるため、指定された言語は Context-Free-Language です。α

_{他に疑問がある場合、またはあなたの言語を誤解した場合はお知らせください}