上下文无关文法 (CFG)

CFG 代表上下文无关文法。它是一种形式文法，用于生成给定形式语言中所有可能的字符串模式。上下文无关文法 G 可以由四个元组定义，如下所示

其中，

G 是文法，它由一组产生式规则组成。它用于生成语言的字符串。

T 是终结符号的最终集合。它用小写字母表示。

V 是非终结符号的最终集合。它用大写字母表示。

P 是一组产生式规则，用于将字符串中的非终结符（在产生式的左侧）替换为其他终结符或非终结符（在产生式的右侧）。

S 是开始符号，用于推导字符串。我们可以通过重复地将非终结符替换为产生式的右侧来推导字符串，直到所有非终结符都被终结符替换。

示例 1

为具有任意数量的 a 的语言构造 CFG，集合为 ∑= {a}。

解决方案

正如我们所知，上述语言的正则表达式是

正则表达式的产生式规则如下

现在，如果我们想推导字符串 "aaaaaa"，我们可以从开始符号开始。

r.e. = a* 可以生成一组字符串 {ε, a, aa, aaa,.....}。我们可以有一个空字符串，因为 S 是一个开始符号，并且规则 2 给出 S → ε。

示例 2

为正则表达式 (0+1)* 构造 CFG

解决方案

CFG 可以由

规则是 0 和 1 的组合，带有开始符号。由于 (0+1)* 表示 {ε, 0, 1, 01, 10, 00, 11, ....}。在这个集合中，ε 是一个字符串，所以在规则中，我们可以设置规则 S → ε。

示例 3

为语言 L = {wcwR | 其中 w € (a, b)*} 构造 CFG。

解决方案

可以为给定语言生成的字符串是 {aacaa, bcb, abcba, bacab, abbcbba, ....}

文法可以是

现在，如果我们想推导字符串 "abbcbba"，我们可以从开始符号开始。

因此，任何这种类型的字符串都可以从给定的产生式规则推导出来。

示例 4

为语言 L = aⁿb²ⁿ 构造 CFG，其中 n>=1。

解决方案

可以为给定语言生成的字符串是 {abb, aabbbb, aaabbbbbb....}。

文法可以是

现在，如果我们想推导字符串 "aabbbb"，我们可以从开始符号开始。