finalS06 

Q1:  

>

 

>

 

Q2: Build an NPDA for L={a^n b^(n+2): n>=0} 

Ideas:  

1. build the PDA directly 

2. build a CFG and then convert it into a PDA, normalize the PDA 

>	p1:=mkNPDA({q0,q1,q2,qf},{a,b},{B,Z0}, table([(q0,\lambda,Z0)={[q1,[B,B,Z0]]}, (q1,a,B)={[q1,[B,B]]}, ## push B in for each a (q1,b,B)={[q2,\lambda]},   ## cannot have a's again (q2,b,B)={[q2,\lambda]},   ## pop B out for each b (q2,\lambda,Z0)={[qf,\lambda]}]), q0,Z0,{qf});

 

(17.1.5.1)

 

>	transitionGraph(p1);

 

>	stringVerificationPDA(p1,[a,a,a,b,b,b,b,b]); stringVerificationPDA(p1,[a,b,a,a,b,b,b,b,b]);;

 

(17.1.5.2)

 

(17.1.5.2)

 

>	g1:=PDA2CFG(p1);

 

(17.1.5.3)

 

>	g1b:=CFG2CNF(g1);

 

(17.1.5.4)

 

>	P:=table([S={[C,b,b],[b,b]}, C={[a,C,b],[\lambda]}]): g2:=mkCFG({S,C},{a,b},S,op(P));

 

(17.1.5.5)

 

>	p2:=CFG2PDA(g2);

 

(17.1.5.6)

 

>	parseCYK(g2,[a,a,a,b,b,b,b,b],table=true,tree=true);

 

>	transitionGraph(p2);

 

Q3: eliminate \lambda rule, unit rules and useless rules 

>	## Question 1 cfg:=mkCFG({V0, V1, V2, V3, V4},{a1, a2, a3},V0,table([V0 = {[lambda], [a1, V3, V2, a2, a3, V4]}, V1 = {[a2, V3, V2]}, V2 = {[lambda], [V2]}, V4 = {[V0], [lambda]}, V3 = {[lambda]}]));

 

>	removeLambdaCFG(cfg); removeUnitCFG(%); removeUselessCFG(%);

 

(17.1.5.7)

 

(17.1.5.7)

 

(17.1.5.7)

 

(17.1.5.7)

 

>	## Question 2 cfg:=mkCFG({V0, V1, V2, V3, V4},{a1, a2, a3},V0,table([V0 = {[lambda], [V3]}, V1 = {[lambda]}, V2 = {[V1, a3]}, V4 = {[V1]}, V3 = {[V4, V3, V0], [a1, a3, V0, V1, V4]}]));

 

>	removeLambdaCFG(cfg); removeUnitCFG(%); removeUselessCFG(%);

 

(17.1.5.8)

 

(17.1.5.8)

 

(17.1.5.8)

 

(17.1.5.8)

 

>

 

Q4: using CYK to parse string 

>	P:=table(): P[S]:={[A,B]}: P[A]:={[B,B],[a]}: P[B]:={[A,B],[b]}: g4:=mkCFG({S,A,B},{a,b},S,op(P));

 

(17.1.5.9)

 

>	parseCYK(g4,[a,a,b,b,b],table=true);

 

(17.1.5.10)

 

(17.1.5.10)

 

>	parseCYK(g4,[a,b,b,a,b],table=true);

 

(17.1.5.11)

 

(17.1.5.11)

 

>	parseCYK(g4,[b,a,b,b,a],table=true);

 

(17.1.5.12)

 

(17.1.5.12)