Pushdown Automata

An illustrative example is your journey through a maze where you take different paths (the input) and place a mark (push into the stack) at each junction. When you reach a dead-end (no available action for the current state), you retreat to the last junction (pop the stack) and try a different path (change state). The maze is solved (input accepted) when an exit path is found (a specific final state is reached).

For example, the expression '((()))' would be accepted by the Pushdown Automata, while the expression '(()()(' would be rejected. This is because for each '(', a corresponding ')' should exist. The Automata pushes every '(' it encounters into the stack. When it encounters a ')', it pops '(‘ from the stack. If the stack is empty when the Automata reads the end of the input, then the string is accepted; else, it is rejected.

Consider a transition labelled as \(1, Z \rightarrow XY\), where 1 is the input symbol, Z is the state's present stack symbol, and XY is the new stack symbol that replaces Z. It shows that on input 1 and if the stack's top symbol is Z, the Automaton will replace the topmost stack symbol with XY.

Consider a DPDA with two states A and B that accepts strings with equal numbers of 0's and 1's. In state A, 0 pushes Z; in state B, 1 pops Z. When all 0's and 1's are balanced, it returns to the state A and accept the string if the last symbol to be popped from the stack is Z (which means all symbols have been matched).

Imagine an NPDA that accepts strings where the number of a's are equal or more than the number of b's, like 'aaabb', 'aab', 'ab', etc. There will be multiple pathways from the initial state to the final state, each depending on whether an 'a' is read and pushed onto the stack or whenever a 'b' is read and 'a' is popped from the stack. When all 'b's are accounted for, all remaining 'a's on the stack are popped, and if the string ends with stack symbol Z, this string is accepted.

To illustrate, consider a DPDA that accepts the language of even-length palindromes. When it reads a symbol \( x \), it pushes \( x \) into the stack. If the following input matches the stack top, it pops \( x \). If all inputs are read and the stack is empty simultaneously, the input is accepted.

An example can illustrate an NPDA's function: imagine an NPDA that accepts the language of palindromes over the alphabet {0, 1}. When it reads a symbol \( x \), it either pushes \( x \) into the stack or enters a state where it attempts to match the remaining inputs with the stack content. In the matching state, if there is an input-match-stack-top scenario, it pops the top. If all inputs are read and the stack is empty simultaneously, the input is accepted.