Automata

1. Given a grammar G S - aaBlbbA|AB|aabb A BAaBla Construct a PDA accepting L(G 2. Recall that the following PDA M accepting language L {w E {01}* : are: &qo, A, 1) = {(geven , 1), (gold, 1)} &qodd, *1: *2) {(geven , *2)) with *,-0. 1, *2-0, 1 - 1) ((even, A)) (leven, 0, 0)(leven, A)) &qeven, A.Zo)-1(Y2. A)} (empty-stack acceptance) &qo.A. Zo) {Ce, )) (make sure that A is accepted) Translate M into a grammar G 1. Given a grammar G S - aaBlbbA|AB|aabb A BAaBla Construct a PDA accepting L(G 2. Recall that the following PDA M accepting language L {w E {01}* : are: &qo, A, 1) = {(geven , 1), (gold, 1)} &qodd, *1: *2) {(geven , *2)) with *,-0. 1, *2-0, 1 - 1) ((even, A)) (leven, 0, 0)(leven, A)) &qeven, A.Zo)-1(Y2. A)} (empty-stack acceptance) &qo.A. Zo) {Ce, )) (make sure that A is accepted) Translate M into a grammar G