Question

1) Given language L = {a"62"n >0} a) Give an informal english description of a PDA for L b) Give a PDA for L

Answer 1

a. This language generates string of characters a and b, where number of b's are twice of number of a's.

For example, L = { abb, aabbbb, aaabbbbbb, .... }

b.

THE PDA CAN be drawn as below.

b,a/E a,a/aa E,Z/z b,a/e q2 91 qf1 a,z/az Ob

• From state q0 to q1, if a is found, we push a onto the stack.
• in q1, if a is found we push aa on to the stack.
• if b is found, we pop from the stack and move to q2.
• if b comes we pop from the stack.

so at encounter of single a, we push two a(aa) onto the stack.

so while popping for each a encountered we pop two b's.

Hence we calculate twice number of b's.

IF THERE IS ANYTHING THAT YOU DO NOY UNDERSTAND, IR NEED MORE HELP THEN PLEASE MENTION IT IN THE COMMENTS SECTION.