为语言 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
案例二
n 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}*}