## Exercise 1›:

Deterministic uniquely-accepting PDA for $\{ a^n b^n \mid n\geq 0 \}$
Write a deterministic uniquely-accepting PDA recognizing the language over $\{a,b\}$ where the first half of each word only contains $a$’s and the second half only contains $b$’s.
Authors: Guillem Godoy / Documentation:
 // In the first problem on PDAs we directly propose a solution, // in order to show which is the syntax to represent PDAs. You // just have to uncomment (remove //) the following seven lines // and submit: // // Z q0 q0 q3 // Z q0 -> Z q1 // Z q1 a -> ZA q1 // A q1 a -> AA q1 // A q1 b -> q2 // A q2 b -> q2 // Z q2 -> Z q3 // // The first line specifies the initial stack symbol (Z), the // initial state (q0) and, finally, the list of accepting states // (q0 and q3). Each of the following lines represents a // transition of the automaton. At the left-hand side of the // symbol -> we have the top of the stack, the state and, // optionally, an input symbol. At the right-hand side of -> we // have the contents that will be pushed to the stack (possibly // empty) and the state reached. For instance, a transition like // Z q0 a -> ZA q1 // would be executed from state q0, popping the symbol 'Z' from // the stack, reading the symbol 'a' from the input, pushing ZA // onto the stack (the symbol 'A' would be at the top) and also // changing into state q1. // Transition rules can also be written more compactly when // several rules share the same origin state and the same destiny // state. Using this idea for all rules, the previous automaton // can be equivalently written of the form: // // Z q0 q0 q3 // q0 -> Z |Z -> q1 // q1 -> Za|ZA, Aa|AA -> q1 // q1 -> Ab| -> q2 // q2 -> Ab| -> q2 // q2 -> Z |Z -> q3 To be able to submit you need to either log in, register, or become a guest.