Theory of Computation2080.15 marksNumerical: PDA construction and acceptanceConstruction of PDA by Final State
Construct a PDA that accepts string over Σ={a,b}\Sigma = \{ a, b \}Σ={a,b} that contains equal number of a's followed by equal number of b's. Show acceptance of aabb and aab.
Construct a PDA that accepts string over Σ={a,b}\Sigma = { a, b }Σ={a,b} that contains equal number of a's followed by equal number of b's. Show acceptance of aabb and aab. [5]
- Alphabet: $\Sigma = {a, b}$ - Language: strings with equal number of $a$'s followed by equal number of $b$'s - Strings to test: $aabb$ and $aab$ $$L = {a^n b^n \mid n \geq 1} = {ab, aabb, aaabbb, \ldots}$$ --- 1. Push each $a$ onto the stack. 2. On the first $b$, start popping $a$'s. 3. O...