CFL - Pushdown Automata Flashcards
When is a word accepted by a PDA?
When it has been read, stack is empty, and automaton is in a final state
What is the main theorem?
Class of languages accepted by pushdown automata
is exactly the class of Context-free languages
What is a PDA?
A sextuple
M = (K, Σ, Γ, ∆, s, F), where:
K is a finite set of states
Σ as an alphabet of input symbols
Γ as an alphabet of stack symbols
s ∈ K is the initial state
F ⊆ K is the set of final states
∆ is a transition relation, a finite set, and may not be a function as a PDA is nondeterministic
∆ ⊆
(K × Σ∗ × Γ∗) × (K × Γ∗)
What is a configuration?
Any tuple:
(q, w, γ) ∈ K × Σ∗ × Γ∗
q ∈ K represents a current state of M, and w ∈ Σ∗ is
unread part of the input,
and γ is a content of the stack
read top-down
What is a transition relation?
acts between two configurations
and hence |- M is a certain binary relation
defined on K × Σ∗ × Γ∗
|-M ⊆ (K × Σ∗ × Γ∗)^2
Given a PDA, a binary relation is a transition relation iff:
For any p, q ∈ K,
u, x ∈ Σ∗,
α, β, γ
(p, ux, βα) |-M
(q, x, γα)
iff
((p, u, β), (q, γ)) ∈ ∆
Define the language L(M)
L(M) = {w ∈ Σ∗ :
(s, w, e) |-M∗ (p, e, e) for certain p ∈ F}
M accepts w ∈ Σ∗
iff. w ∈ L(M)
M accepts w ∈ Σ∗
iff computation
in M such that it starts with w and with empty stack ((s, w, e))
and it ends in a final state after reading w and emptying all
of the stack
((p, e, e) for certain p ∈ F )
PDA-FA Theorem
The class FA of finite automata is a proper subset of the
class PDA of pushdown automata, i.e.
FA ⊂ PDA
Proof of PDA-FA Theorem
Show that every FA automaton is a PDA automaton that operates on an empty stack (Slide 20, Lecture 10)
Show the transition for “Push a”
((p, u, e), (q, a))
Show the transition for “Pop a”
((p, u, a), (q, e))
Show the transition for “Compare and pop a”
((p, a, a), (q, e))
Show the transition for “Compare a with b and pop b”
((p, a, b), (q, e))
What does
((p, u, B)), (q, r)) ∈ Δ mean?
M in state p:
1) reads u
2) replaces B with r at the top of the stack
3) goes to the state q
Lemma 1 of PDA main theorem
Each CFL is accepted by some PD automaton
Lemma 2 of PDA main theorem
If a language is accepted by a PDA, it is a CFL
What 2 views does the PDA Main Theorem prove the equivalency of?
2 views of CFL 1. A language L is CF if it is generated by a CFG (defn.)
2. A language L is CF if it is accepted by a PDA.
Closure Theorems of CFL
Closure Theorem 1
The context-free languages are closed under union,
concatenation, and Kleene star
Closure Theorem 2
The intersection of a context-free language with a regular
language is a context-free language
Closure Theorem 3
The context-free languages are not closed under
intersection and complementation
Not Context-free Languages theorem 4:
By the pumping lemma, the following are not CF:
L1 = {a^ib^ja^ib^j:
i, j ≥ 0}
L2 = {a^p : p is prime}
L3 = {a^(n^2) : n ≥ 0}
L4 = {www : w∈{a,b}*}
Parikh Theorem
Used because: some very simple non-context-free
languages which cannot be shown not to be context-free by
a direct application of the Pumping Lemma
If Ψ(L) is not semilinear, then L is not context-free
Theorem 6 using Parikh Theorem
Every CFL over a 1 symbol alphabet
is regular
L = {w ∈ {a, b}∗
: w has the same number of a’s and b’s }
Proved CFL by constructing a PDA
and applying the Main Theorem
L = {w ∈ {a, b, c}∗
: w has the same number of a’s, b’s and c’s }
L = {a^pb^n
: p ∈ Prime, n > p}
Proved NOT CFL by PL
