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

  • Z时代
  • 2024-01-10
  • 分类：综合

上下文无关文法是一个四元组 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

案例二

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}*}

以上是 为语言 L = {anbm| 生成上下文无关文法 m≠n}？ 的全部内容， 来源链接： utcz.com/z/358116.html

回到顶部