CFG2PDA 

>	cfg:=mkCFG({S},{a,b},S,table([S={\lambda,[a,S,a],[b,S,b]}]));

 

(12.1.1)

 

>	transitionGraph(CFG2PDA(cfg));

 

>	#L={a^n b^n:n>0} P:=table(): P[S]:={[a,S,b],[a,b]}: cfg01:=mkCFG({S},{a,b},S,op(P)); CFG2CNF(cfg01);

 

(12.1.2)

 

(12.1.2)

 

>	pda30:=CFG2PDA(cfg01); transitionGraph(pda30);

 

>

transitionGraph(NPDA({q_f, q_1, q_0,q_w},{a, b},{S1a, S1b, S_1, z_0, S},table([(q_1, lambda, S_1) = {[q_1, [S, S1b]]}, (q_1, lambda, S) = {[q_1, [S1a, S1b]], [q_1, [S1a, S_1]]}, (q_1, b, S1b) = {[q_1, lambda]}, (q_1, a, S1a) = {[q_1, lambda]}, (q_0, lambda, z_0) = {[q_1, [S, z_0]]}, (q_1, lambda, z_0) = {[q_f, lambda]}]),q_0,z_0,{q_f}));

 

>	CFG2CNF(cfg01);

 

(12.1.3)

 

>	## Question 1 cfg1:=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]}]));

 

(12.1.4)

 

>	pda1:=CFG2PDA(cfg1);transitionGraph(pda1);

 

>	CFG2CNF(cfg1);

 

(12.1.5)

 

PDA2CFG 

First, convert cfg01 into a PDA.  

Second, convert the PDA back into a CFG and  

Third, test using parseCYK 

>	#L={a^n b^n:n>0} P:=table(): P[S]:={[a,S,b],[a,b]}: cfg01:=mkCFG({S},{a,b},S,op(P)); pda30:=CFG2PDA(cfg01); transitionGraph(pda30); cfg30:=PDA2CFG(pda30);

 

>	w:=[a,a,a,b,b,b]: parseCYK(cfg30,w,tree=true);

 

>	w:=[a,a,a,b,b,a]: parseCYK(cfg30,w);

 

(12.2.1)

 

>	w:=[b,a,a,a,b,b]: parseCYK(cfg30,w);

 

(12.2.2)

 

>	CFG2CNF(cfg30);

 

(12.2.3)

 

>	CFG2CNF(cfg01);

 

(12.2.4)

 

>

 

>

InternalStates:={q0,q1,q2,q3,q4}: Alphabet:={a,b}: StackAlphabet:={0,1}: delta:=`delta`: delta[(q0,a,0)]:={[q1,[1,0,1,1]],[q3,\lambda]}: delta[(q0,\lambda,0)]:={[q3,\lambda],[q3,0]}: delta[(q1,a,1)]:={[q1,[1,1]]}: delta[(q1,b,1)]:={[q2,\lambda]}: delta[(q2,b,1)]:={[q2,\lambda]}: delta[(q2,\lambda,0)]:={[q3,\lambda]}: StackStartSymbol:=0: InitialState := q0: FinalStates:={}: npda:=mkNPDA(InternalStates,Alphabet,StackAlphabet,op(delta),  InitialState,StackStartSymbol,FinalStates);

 

(12.2.5)

 

>	type(npda,PDA);

 

(12.2.6)

 

>	cfg:=PDA2CFG(npda);

 

(12.2.7)

 

>	CFG2CNF(cfg);

 

(12.2.8)

 

>