语言描述如下：
{ 1n0m | n ≥ m ≥ 1 }
转化为上下文无关文法方法如下：
1 、拆分语言
{1^n│n≥0}
{1^m 0^m |m≥1｝
据此得到文法:
G : S->1S|10|1A0
A->1A0|10
PDA M=(Q,Σ,Γ,δ,q0,Z0,F)
所以 Σ={0,1}
2022-05-28 12:23:00
18KB
1
1、无产生式的上下文无关文法要满足条件
若P中含S ，则S不出现在任何产生式右部，其中S为文法的开始符号；
P中不再含有其它任何产生式。
2、构造无产生式的上下文无关文法变换算法：
G=(VN,VT,P,S) G’=(V’N,V’T,P’,S’)
（1）由文法G找出所有经过若干步推导能推出的非终结符，放在V0集合中。
2022-05-21 17:04:38
1.65MB
1