Homework answers / question archive / Using the method that was presented in class, contrast a pushdown automata (with only one state) that accepts the set of strings generated by the following grammar (acceptance should be by empty stack): G=({S,A},{a,b},P,5) Where P is the following set of productions: S->AA A->abla 2) (15 points) Consider the following pushdown automaton N: N={{90,91,92},{a,b},{A,B,1},8,90,1,92} 8(90,0,1)=(90,AL) 8(90,b,A)=(90,€) 8(90,€,1)=(92,8) 8(90,a,A)=(90,AA) 8(90,b,1)=(92,B1) 8(91,6,B)=191,B) a

Using the method that was presented in class, contrast a pushdown automata (with only one state) that accepts the set of strings generated by the following grammar (acceptance should be by empty stack): G=({S,A},{a,b},P,5) Where P is the following set of productions: S->AA A->abla 2) (15 points) Consider the following pushdown automaton N: N={{90,91,92},{a,b},{A,B,1},8,90,1,92} 8(90,0,1)=(90,AL) 8(90,b,A)=(90,€) 8(90,€,1)=(92,8) 8(90,a,A)=(90,AA) 8(90,b,1)=(92,B1) 8(91,6,B)=191,B) a

Computer Science

Share With

Using the method that was presented in class, contrast a pushdown automata (with only one state) that accepts the set of strings generated by the following grammar (acceptance should be by empty stack): G=({S,A},{a,b},P,5) Where P is the following set of productions: S->AA A->abla 2) (15 points) Consider the following pushdown automaton N: N={{90,91,92},{a,b},{A,B,1},8,90,1,92} 8(90,0,1)=(90,AL) 8(90,b,A)=(90,€) 8(90,€,1)=(92,8) 8(90,a,A)=(90,AA) 8(90,b,1)=(92,B1) 8(91,6,B)=191,B) a. Modify N so that it meets the following restrictions: every move either pops the stack or increases the depth of the stack by one element. b. Using the method that was presented in class, contstruct a context free grammar G such that L(G) is the set of strings accepted by the automaton. At the end, give the grammar with all useless productions removed, where useless productions are those that contain a non-terminal that is not part of the left hand side of any production. C. Side by side, show the derivation of the string aaabbb by the grammar G and the configurations of the automaton when processing the string aaabbb.