上下文无关文法的例子

上下文无关文法的例子

例子 1
一个简单的上下文无关文法的例子是：S -> aSb | ε。这个文法产生了语言 {anbn : n ≥ 0} 。不难证明这个语言不是正规的。
例子 2
这个例子可以产生变量 x,y,z 的算术表达式：
S -> T + S | T - S | T
T -> T * T | T / T | ( S ) | x | y | z
例如字串 ( x + y ) * x - z * y / ( x + x ) 就可以用这个文法来产生。
例子 3
字母表 {a,b} 上 a 和 b 数目不相等的所有字串可以由下述文法产生：
S -> U | V
U -> TaU | TaT
V -> TbV | TbT
T -> aTbT | bTaT | ε
这里 T 可以产生 a 和 b 数目相等的所有字串，U 可以产生 a 的数目多于 b 的数目的所有字串， V 可以产生 a 的数目少于 b 的数目的所有字串。