CFL - Pushdown Automata

Question 1

When is a word accepted by a PDA?

Answer 1

When it has been read, stack is empty, and automaton is in a final state

Question 2

What is the main theorem?

Answer 2

Class of languages accepted by pushdown automata
is exactly the class of Context-free languages

Question 3

What is a PDA?

Answer 3

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 × Γ∗)

Question 4

What is a configuration?

Answer 4

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

Question 5

What is a transition relation?

Answer 5

acts between two configurations
and hence |- M is a certain binary relation
defined on K × Σ∗ × Γ∗
|-M ⊆ (K × Σ∗ × Γ∗)^2

Question 6

Given a PDA, a binary relation is a transition relation iff:

Answer 6

For any p, q ∈ K,
u, x ∈ Σ∗,
α, β, γ
(p, ux, βα) |-M
(q, x, γα)
iff
((p, u, β), (q, γ)) ∈ ∆

Question 7

Define the language L(M)

Answer 7

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 )

Question 8

PDA-FA Theorem

Answer 8

The class FA of finite automata is a proper subset of the
class PDA of pushdown automata, i.e.
FA ⊂ PDA

Question 9

Proof of PDA-FA Theorem

Answer 9

Show that every FA automaton is a PDA automaton that operates on an empty stack (Slide 20, Lecture 10)

Question 10

Show the transition for “Push a”

Answer 10

((p, u, e), (q, a))

Question 11

Show the transition for “Pop a”

Answer 11

((p, u, a), (q, e))

Question 12

Show the transition for “Compare and pop a”

Answer 12

((p, a, a), (q, e))

Question 13

Show the transition for “Compare a with b and pop b”

Answer 13

((p, a, b), (q, e))

Question 14

What does
((p, u, B)), (q, r)) ∈ Δ mean?

Answer 14

M in state p:
1) reads u
2) replaces B with r at the top of the stack
3) goes to the state q

Question 15

Lemma 1 of PDA main theorem

Answer 15

Each CFL is accepted by some PD automaton

Question 16

Lemma 2 of PDA main theorem

Answer 16

If a language is accepted by a PDA, it is a CFL

Question 17

What 2 views does the PDA Main Theorem prove the equivalency of?

Answer 17

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.

Question 18

Closure Theorems of CFL

Answer 18

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

Question 19

Not Context-free Languages theorem 4:

Answer 19

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}*}

Question 20

Parikh Theorem

Answer 20

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

Question 21

Theorem 6 using Parikh Theorem

Answer 21

Every CFL over a 1 symbol alphabet
is regular

Question 22

L = {w ∈ {a, b}∗
: w has the same number of a’s and b’s }

Answer 22

Proved CFL by constructing a PDA
and applying the Main Theorem

Question 23

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}

Answer 23

Proved NOT CFL by PL