Chapter 9 - Pushdown Automata Flashcards
What is a pushdown automata?
A pushdown automata is a finite automata, but with a stack i.e. a data structure that can be used to store an arbitrary number of symbols (hence they have an infinite amount of states), but can only be accessed in a LIFO fashion. Can only recognise Context-free languages.
What makes up a pushdown automata?
A finite set of states (Q)
A finite set of input symbols (the alphabet, can also be written as sigma)
A finite set of stack symbols (represented as a weird capital R)
A transition function
An initial state (Q0)
An initial stack symbol (Z0)
A set of final states (F)
How does a PDA work?
The state of the PDA is given by the state it is in, the input string that still has yet to be processed, and the contents of the stack.
What is an ID?
An ID is an Instantaneous Description, made up of the state, the input string and the stack contents.
What is a relation?
A relation is a descriptor that describes how the PDA can change from one PDA to another
What are the two acceptance methods for a PDA?
Acceptance by final state:
That is, the PDA accepts the word if there is any sequence of IDs starting from the initial state and leading to any of the final states. The stack here doesn’t matter.
Acceptance by empty stack:
That is, the PDA accepts the word if there is a sequence of IDs starting from the initial state and leading to a state where the word to be processed and the stack are both empty. IN this case, the final state does not matter.
However, both acceptance methods accept the same class of language.
What is a deterministic PDA?
A deterministic PDA (DPDA) is a PDA where it ‘has no choice’ i.e. if there are multiple correct options available, then it is not a deterministic PDA.
