Introduction to Formal Languages and Automata.

Complete the transition tables and configuration traces for the two Pushdown Automata (PDA) below. Both PDAs employ nondeterminism for the processing of input strings. PDA-1: This PDA is to accept the context-free language a2"bn+1 where n 2 1 Transition Table for the nondet, PDA: State qo q1 q1 q2 q2 q2 Input Top of StackMove 1 (q1, aZ) 4 (q2, ) 6 All others: no move accept in q3 Configuration Trace for input string aaaabbb: I- (q1, aabbb, aZ) |--(q 1,--, (q1, bbb, aaz) |--(q2, , Z) |--(q 3, , Z). Accept