为语言 L = {anbm| m≠n} 生成一个上下文无关文法？

上下文无关文法是一个四元组 G = (N, T, P, S)，

其中，

  • N 是非终结符的有限集合，

  • T 是终结符的有限集合，N ∩ T = ∅，

  • P 是形如 A → α 的产生式的有限集合，

  • 其中 A ∈ N，α ∈ (N ∪ T)*，

  • S 是开始符号，S ∈ N。

为语言 L = {anbm| m ≠n} 构造一个上下文无关文法

情况 1

n > m - 我们生成一个具有相同数量的 a 和 b 的字符串，并在左侧添加额外的 a -

S → AS1, S1 → aS1b, S1 → λ, A → aA, A → a

情况 2

n < m - 我们在右侧添加额外的 b -

S → S1B, B → bB, B → b.

典型推导

S ⇒ AS1 ⇒ aAS1 ⇒ aaAS1 ⇒ aaaS1 ⇒ aaaaS1b ⇒ aaaab 或

S ⇒ S1B ⇒ aS1bB ⇒ aS1bb ⇒ abb

考虑另一个关于 上下文无关文法和语言 的例子

  • 每个正则文法都是上下文无关的，因此正则语言也是上下文无关的。

  • 正则语言族是上下文无关语言族的一个真子集。

示例

令 G = ({S}, {a, b}, P, S)，其中

P = {S → aSa, S → bSb, S → λ}。

典型推导 - S ⇒ aSa ⇒ aaSaa ⇒ aabSbaa ⇒ aabbaa。

L(G) = {wwR | w ∈ {a, b}*}

更新于: 2021-06-16

6K+ 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告