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 的序列？

这两个子问题如何组合成一个上下文无关文法？

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 -> λ)

语法在语言中's 和'sG1的数量和位置之间建立所需的关系，然后以应用规则结束。acL1S -> λ

G1考虑如何通过应用 rule 来终止派生S -> λ，以及如何生成m >= 0 b's 序列而不是空字符串。这是一个稍微更普遍的问题的解决方案。假设我们有一种L2由语法生成的语言

G2 = <V,N,S2,P>

为了生成由相等数量的' 和'L2包围的字符串，可以将的规则扩充如下以获得语法：acG1G1'

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

为了解决您的问题，让我们成为生成它L2的语言{b}*和常规语法。G2

2 回答 2