2.2 PUSHDOWN AUTOMATA (Staflavélar) Flashcards
What are pushdown automata?
They are like nondeterministic finite automata but have an extra component called a stack.
What does the stack do in pushdown automata?
The stack provides additional memory beyond the finite amount available in the control. The stack allows pushdown automata to recognize some nonregular languages.
Why is it useful that pushdown automata are equivalent in power to context-free grammars?
Because it gives us two options for proving that a language is context free.
We can give either a context-free grammar generating it or a push- down automaton recognizing it.
Certain languages are more easily described in terms of generators, whereas others are more easily described by recognizers.
What can pushdown automaton (PDA) do?
A pushdown automaton (PDA) can write symbols on the stack and read them back later.
How does pushdown automaton put things on the stack?
Writing a symbol “pushes down” all the other symbols on the stack.
What is pushing and popping?
Writing a symbol on the stack is of- ten referred to as pushing the symbol, and removing a symbol is referred to as popping it.
In other words a stack is a “last in, first out” storage device.
What does that mean?
All access to the stack, for both reading and writing, may be done only at the top.
A pushdown automaton is a 6-tuple (Q, Σ, Γ, δ, q0, F ), where
Q, Σ, Γ, and F are all finite sets, and
1. Q is the set of states,
2. Σ is the input alphabet,
3. Γ is the stack alphabet,
4. δ: Q × Σε × Γε−→P(Q × Γε) is the transition function,
5. q0 ∈ Q is the start state, and
6. F ⊆ Q is the set of accept states.
If a language is context free, then some pushdown automaton recognizes it.
Because every regular language is recognized by a finite automaton and every finite automaton is automatically a pushdown automaton that simply ignores its stack, we now know that every regular language is also a context-free language.
How is the pumping lemma different for context-free languages?
This time the meaning of pumped is a bit more com- plex. It means that the string can be divided into five parts so that the second and the fourth parts may be repeated together any number of times and the resulting string still remains in the language.
Pumping lemma for context-free languages :
If A is a context-free language, then there is a number p (the pumping length) where, if s is any string in A of length at least p, then s may be divided into five pieces s = uvxyz satisfying the conditions
1.for each i≥0, uv^ixy^iz∈A,
2. |vy| > 0, and
3. |vxy| ≤ p.
