时间戳

首页 > 解决方案 > 从语言生成上下文无关语法

context-free-grammar - 从语言生成上下文无关语法

问题描述

我需要为每个示例提供一个上下文无关的语法：

L1 = {a^hb^ka^mb^n : h + k = m + n}
L2 = {a^ib^ja^k : (i = j and k >= 0) or (i >= 0 and j > k)}

我已经完成了许多简单的示例，并且提高了从语法生成 CFG 的技能。我通常从解决最简单的情况开始，然后从那里开始构建。但是，我很困惑我可以从哪里开始找到这些问题的解决方案。

标签： context-free-grammar

解决方案

对于第一个，想象从外向内剥离符号。我们开始剥离 a 和 b 对：

S -> aSb

如果我们先剥离所有的第一，我们需要进入一个新的状态；否则，如果我们先剥掉所有的b，我们需要进入一个新的状态；否则，如果我们同时剥离两个，我们可以切换到剥离反向对：

S -> aSb
S -> aXa | bYb
S -> bZa

如果我们最终做 S -> aXa，我们需要用尽左边的 a 才能接受；否则，我们可以继续从两端剥离 a：

S -> aSb | aXa | bYb | bZa
X -> aXa | bZa

同样对于 Y：

S -> aSb | aXa | bYb | bZa
X -> aXa | bZa
Y -> bYb | bZa

现在对于 Z，我们只需要确保以空字符串结尾：

S -> aSb | aXa | bYb | bZa
X -> aXa | bZa
Y -> bYb | bZa
Z -> bZa | e

如何证明这是正确的？首先，争辩说这只会产生语言中的字符串。这里的一个证明想法是注意最后一个产生式是 Z -> e 并且到目前为止，我们总是在它的两侧添加相同数量的符号；同样，在左边，我们只能在 a 之后添加 b，而在右边，我们只能在 b 之前添加 a。然后，争辩说这会产生语言中的所有字符串。这里的一个证明思路是描述在一般情况下如何推导出 a^hb^ka^mb^n。分别考虑 h < n、h = n 和 h > n，并且在每种情况下分别考虑 k < m、k = m 和 k > m。

对于第二个，您的第一步应该是将其拆分为两种语言并摆脱析取：

L2 = A union B
A = {a^ib^ja^k : (i = j and k >= 0)}
B = {a^ib^ja^k : (i >= 0 and j > k)}

现在，找到 A 的语法：

A -> Aa | A'
A' -> aA'b | e

接下来，找到 B 的语法：

B -> aB | B'
B' -> bB'a | b

然后，编写将 S 连接到 A 或 B 的 S 的语法：

S -> A | B
A -> Aa | A'
A' -> aA'b | e
B -> aB | B'
B' -> bB'a | b

这一点的证明留作练习。

推荐阅读