Context Free Languages

Question 1

Definition 2.1 (Context-Free Grammar)

Answer 1

A context-free grammar (CFG) is a 4-tuple (V, Σ, R, S), where

1. V is a finite set called the variables,
2. Σ is a finite set, disjoint from V , called the terminals,
3. R is a finite set of (substitution) rules / productions of the form

                               A → w ,

with A ∈ V and w ∈ (V ∪ Σ)∗ (i.e. w = ε is possible), and 4. S ∈ V is the start variable.

Question 2

Definition 2.2

Answer 2

Let G = (V, Σ, R, S) be a CFG, u, v, w ∈ (V ∪ Σ)∗ and A ∈ V .

If A → w is a rule of the grammar, we say that uAv yields uwv, written

                           uAv ⇒ uwv .

We write
u∗⇒ v ,

if u = v or if a sequence u1, u2, . . . , uk ∈ (V ∪ Σ)∗
, k ≥ 0 exists, such that
u ⇒ u1 ⇒ u2 ⇒ . . . ⇒ uk ⇒ v .
The language of the grammar G, L(G), is

L(G) = {w ∈ Σ∗ | S∗⇒ w} .

A language that is generated by a CFG is called context-free language (CFL).

Question 3

`Definition 2.3 (Chomsky Normal Form)

Answer 3

A context-free grammar G = (V, Σ, R, S) is in Chomsky normal form
if every rule is of the form
A → BC (2.1)
A → a (2.2)
where a ∈ Σ, A ∈ V , B, C ∈ V \ S. In addition, we permit the rule
S → ε .

Question 4

Theorem 2.1 Any context-free language is generated by a …

Answer 4

context-free grammar in Chomsky normal form.

Question 5

Definition 2.4 (Pushdown Automata)

Answer 5

A pushdown automaton (PDA) 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
(with Σε = Σ ∪ {ε}, Γε = Γ ∪ {ε}),
5. q0 ∈ Q is the start state, and
6. F ⊆ Q is the set of accept states.

Question 6

Definition 2.5 (Strings accepted by PDA P)

Answer 6

Let P = (Q, Σ, Γ, δ, q0, F) be a P DA. P accepts an input string w, if w can be written as w = y1y2 · · · ym (yi ∈ Σε) and sequences of states r0, r1, . . . , rm ∈ Q and strings s0, s1, . . . sm ∈ Γ∗ (representing the sequence of stack contents) exist such that

1. r0 = q0, s0 = ε, (P starts in start state with empty stack.)
2. for i = 0, . . . , m − 1 (a, b ∈ Γε, t ∈ Γ∗):
   (ri+1, b) ∈ δ(ri, yi+1, a), while si = at and si+1 = bt, and
   (State / stack change follows transition function.)
3. rm ∈ F. (P ends up in accept state.)
   If P does not accept w, it rejects it.

Question 7

Definition 2.6 (Computation branch of a PDA)

Answer 7

Let P = (Q, Σ, Γ, δ, q0, F) be a PDA and
w be an input string over alphabet Σ.
A computation branch of P on w allows for a modification of the input string w as
a string w = y1y2 · · · ym, yi ∈ Σε and is a sequence of tuples of states and stack contents c = (r0, s0),(r1, s1), . . . ,(rm, sm), such that the following two conditions hold:
1. r0 = q0, s0 = ε
2. for i = 0, . . . , m − 1 (a, b ∈ Γε, t ∈ Γ∗):
(ri+1, b) ∈ δ(ri, yi+1, a), while si = at and si+1 = bt, and

We call c an accepting computation branch, if rm ∈ F, otherwise we call it a rejecting computation branch.

Question 8

Definition 2.7 (Language of a PDA)

Answer 8

Let P = (Q, Σ, Γ, δ, q0, F) be a PDA. The language
of P, L(P), that is recognized by P is defined by
L(P) = {w ∈ Σ∗| w accepted by P} .

Question 9

Theorem 2.2 A language is context-free if and only if …

Answer 9

some pushdown automaton recognizes it.