{abc*} 的上下文无关文法 - {a^n b^n c^n | n >=0}

Question

我遇到了这个问题。我相信它告诉我，不能生成任何包含 a、b 和 c 的字符串。这是由于减去第二组。

来自新形成的 CFG 的一个好的字符串应该是 aaabbc 或 abbbcc 等等。

所以我试着把问题分成三个部分...

单一州

a.) S(1) -> aS(1) | a | ^
b.) S(2) -> bS(2) | b | ^
c.) S(3) -> cS(2) | b | ^

两国

a.) S(4) -> aS(4)b | S(1) | S(2)
b.) S(5) -> bS(5)c | S(2)
c.) S(6) -> aS(6)c | S(3) | S(1)

州w/AB州

a.) S(7) -> S(1) | S(4)S(6)
b.) S(8) -> S(2) | S(5)S(6)
c.) S(9) -> S(3) | S(6)S(3)

初始状态为...

S ->  S(7) | S(8) | S(9)

但是我在构建像 aaaabbbcc 这样的字符串时遇到了问题...

我是否错误地构建了 CFG？我觉得我走在正确的轨道上，但现在我迷路了。

Answer 1

这种语言的更简单的表达方式是：

{aⁿb^m c^* | n≠m}∪{a^*bⁿc^m | n≠m}

（上面用Kleene星号估计是滥用记法，本来我写的是用第三个整型变量，但我觉得星号更清晰。）

现在，{aⁿb^m | n ≠ m } 就是 aⁿ(a ⁺|b⁺)bⁿ

所以完整的表达式可以写成 aⁿ(a⁺|b ⁺)bⁿc^* | a^*bⁿ(b⁺|c⁺)cⁿ

将所有这些放在一个 CFG 中有点乏味，所以 ~~我把它留到 reader~~等了七年才写出来。这几乎完全是机械的。

S -> A R | L C
# "Left" a^mb^n m ≠ n
L -> a A | b B | a L b
# "Right" b^mc^n m ≠ n
R -> b B | c C | b R c
# zero or more a's (b's, c's)
A -> a A | ε
B -> b B | ε
C -> c C | ε

从中制作 DFA（或更准确地说是确定性下推自动机）可能更棘手，因为 CFG 是模棱两可的。事实上，该语言的 every CFG 是不明确的。但是制定 NDPA 是没有问题的。

Answer 2

所以我把问题分成了2个子问题

a的数量与b的数量不同。因此a和c或b和c可以相同。

b的数量与c的数量不同。因此a和b或a和c可以相同。

Edit：更正式的说法是 Rici {aⁿb^mc^* | n≠m}∪{a^*bⁿc^m | n≠m}

//a and b is different
S-->XR
//b and c is different
S-->DY

//Genarates a string where a is more than b
X--> aXb | A
A --> aA  | a

//Genarates a string where b is more than a
X--> bXa | B
B --> bB  | b

//Genarates a string where b is more than c
Y--> bYc | B
B --> bB  | b

//Genarates a string where c is more than b
Y--> cYb | C
C --> cC  | c

R-->Rc|c|^
D-->Da|a|^

Answer 3

可以使用给定的产生式构造 a^n b^n c^n 语言的上下文无关语法。

S -> aSc | X
X -> BX
X -> null

使用上面的产生式你可以生成a^n b^n c^n。假设我们正在生成 a^2 b^2 c^2。我们将从S.

开始

= aSc
= aaScc ; aSc
= aaXcc ; S -> X
= aabXcc ; X -> bX
= aabbXcc ; X -> bX
= aabb(null)cc ; X -> null
= aabbcc

Answer 4

默多克上面的答案非常接近，但在某些情况下失败了。例如，它可以生成 a、b 和 aabcc，但不能生成 c、abbcc 或 bc，即使它应该能够生成。（JFlap 是一个很棒的软件，我用它来快速测试我正在构造的语法上的不同字符串，它对形式语言和计算理论中的许多其他概念也很有帮助。）使用 Murdock 的 CFG，字母也可能以不同的顺序出现，但问题陈述强制所有 a 出现在第一位，然后是所有 b，最后是所有 c。

丹麦语 Ahmed 似乎误解了这个问题，并试图为 a、b 和 c 的数量相等的语言构建一个 CFG。在他们的头脑中，我的讲师说不可能为此构建一个 CFG。 Danish的CFG对于a = b = c是不正确的，因为它可以通过S -> X自己生成一个'b'； X -> BX； X -> null（还假设大写字母 B 是终端 b。）

这是我的答案，它添加并调整了 Murdock 的 CFG 的一些组件，使其对问题有效。

S=XR|DY|WR|DZ
X=aXb|A
A=aA|a
W=aWb|B
B=bB|b
Y=bYc|B
Z=bZc|C
C=cC|c
R=Rc|c|epsilon
D=Da|a|epsilon

{abc*} 的上下文无关文法 - {a^n b^n c^n | n >=0}

Context free grammar for {abc*} - {a^n b^n c^n | n >=0}

grammar

context-free-grammar

{a*b*c*} 的上下文无关文法 - {a^n b^n c^n | n >=0}

Context free grammar for {a*b*c*} - {a^n b^n c^n | n >=0}

grammar

context-free-grammar

{abc*} 的上下文无关文法 - {a^n b^n c^n | n >=0}

Context free grammar for {abc*} - {a^n b^n c^n | n >=0}