2: Context-free languages and pushdown automata

Question 1

What is a stack?

Answer 1

A linear data structure following a last in, first out (LIFO) ordering. You push items (here, letters) onto the top of the stack before popping them off.

Question 2

What is a PDA?

Answer 2

A pushdown automaton is a mechanical device that uses a stack data structure to model context-free grammars in theoretical Maths and Computer Science.

Question 3

How do you define a PDA?

Answer 3

A tuple of 6 items, P = (Q, Σ, Γ, δ, q0, T), where:

Q is a finite set of states

Σ is a finite set compromising the input alphabet; the input to the PDA P must be a word ∈ Σ*

Γ is a finite set compromising the stack alphabet; the word on the stack at any point ∈ Γ*

δ is a nondeterministic transition function following:
δ: Q x ΣЄ x ΓЄ →P(Q x ΓЄ)

q0 is the start state; q0 ∈ Q

T is the set of accept states, so it a subset of Q: T ⊆ Q

Question 4

When does a PDA accept an input word?

Answer 4

A PDA accepts when each letter in the input word is in the input alphabet or the empty word, the input symbols cause a set of state transitions such that the final state of the PDA is an accepting state (in the set of accepting states, T), and the PDA transitions properly according to its transition function, δ.

Question 5

If P is a PDA what is the language L(P)?

Answer 5

The language L(P) is the set of all words in Σ* that P accepts; Σ = input alphabet, so Σ* = words that can be made from the input alphabet.

Question 6

True/false: PDAs recognise all regular languages

Answer 6

True

Question 7

True/false: PDAs can’t recognise any non-regular languages

Answer 7

False. PDAs can recognise some non-regular languages

Question 8

Prove that PDAs recognise all regular languages.

Answer 8

1. Let a DFA M = (A, S, F, s0, T). We mimic this DFA with PDA P. The 6-tuple defining P is (S, A, ∅, δ, s0, T), where δ is defined as follows: For each s ∈ S, and for each a ∈ A, set δ(s, a, ϵ) = {(F(a, s), ϵ)}. For all s ∈ S, set δ(s, ϵ, ϵ) = ∅. Then on input any w ∈ A*, the PDA P goes through the same sequence of states as M, and never looks at the stack.

Question 9

Prove that PDAs can recognise some non-regular languages

Answer 9

We saw in Chapter 1 Example 5.3 that {a ^ m b ^ m : m > 0} is not a regular language, so {0 ^ n 1 ^ n : n ≥ 0} is also not regular. However, in Example 1.3 we have constructed a PDA to accept {0 ^ n 1 ^ n : n ≥ 0}.

Question 10

How does a PDA work?

Answer 10

Stack initialised with a symbol to mark end of stack (i.e. empty), usually $. You then iteratively read each symbol in the input word and use the transition function to know which letters (if any) to pop from the stack and push to it, and then which state is transitioned to. If the PDA reaches an invalid branch or computation or halts in a state not in the accept states then it rejects. Otherwise, it can enter an infinite loop or accept, if it terminates in an accept state.

Question 11

What is a CFG?

Answer 11

Context-free grammars are formal sets of rules defining how to build strings in a language, and thereby the languages themselves. All languages defined by CFGs are accepted by PDAs.

Question 12

How do CFGs differ from regular expressions?

Answer 12

Rather than being static patterns that allow you to tell whether a word is in a language, CFGs describe how to build up valid words in the language.

Question 13

How do you define CFGs?

Answer 13

As a tuple of 4 items, (N, Σ, R, S)

N = a finite set of variables

Σ = finite set of terminals; N ∩ Σ = ∅, i.e. no items in both N and Σ

R = finite set of production rules A→w, where A ∈ N and w ∈ (N ∪ Σ)*; A is a variable in N, and w is a variable or terminal in either N or Σ (via the union of the two)

A is the start variable; S ∈ N.

Question 14

What is a context-free language?

Answer 14

A language (set of possible words generated from an alphabet of symbols) for which there is a CFG equivalent to it.

Question 15

True/false: a language is context-free if and only if a pushdown automaton recognises it.

Answer 15

True

Question 16

True/false: the set of context-free languages is a proper subset of the class of regular languages

Answer 16

False. The set of regular languages is a proper subset of the set of context-free languages

Question 17

Prove that the set of regular languages is a proper subset of the set of context-free languages.

Answer 17

Regular languages are a proper subset of languages recognised by PDAs. We will show how to convert CFGs to PDAs, showing that the set of regular languages is, therefore, a proper subset of the set of context-free languages.

Let the context-free grammar be G = (V, Σ, R, S). We will design a pushdown automaton P which mimics all possible left-most derivations of G. (A leftmost derivation is one where at every step the leftmost remaining variable is replaced. One can show that if w ∈ L(G) then there is a left-most derivation which produces w). The PDA P uses nondeterminism to mimic all of them at once. It will accept an input word w if one of the derivations produces w.

The PDA P will use its stack to store each step of the derivations: it will pop the variable that it wants to replace, and push on the right-hand side of the corresponding rule of the CFG. This is described in Step 3, below, where we show stack.

There is one further complication, due to the fact that P can only read the top letter of the stack: the next variable that P wishes to replace could be hidden under some terminals. The PDA deals with this by matching the terminals at the top of the stack to the letters of w, as they are produced: reading the stack from top to bottom, these will appear in the same order as they are in w. More specifically, if
P is in state qloop (see Step 1, below), and there is a terminal a 2 ⌃ on the top of the stack, P reads the next letter b of w. If a = b then P pops a o↵ the stack: see Step 4, below. If a 6= b, then this branch of computation rejects w.
1. Start with four states: q0, q1, qloop and qaccept. Make q0 the start state, and
qaccept the only accept state.
Most of the work of P happens at qloop. Whenever P is in qloop the stack
will contain the result of a derivation in G (except with some initial terminals
missing, if they have already been matched with the input word w).
2. Put an arrow labelled ✏, ✏ ! $ from q0 to q1, and an arrow labelled ✏, ✏ ! S
from q1 to qloop.
We mark the bottom of the stack, and then start the derivation with S.
Put an arrow labelled ✏, $ ! ✏ from qloop to qaccept.
Once the stack is empty we accept the input word if we’ve read, and matched,
all of its letters.
These are the only arrows to or from q0, q1, and qaccept.
3. For each rule in R of the form A ! u, where A 2 V and u 2 (V [ ⌃)⇤, add a
chain of new states and arrows as follows:
(a) If u = u1u2 …un, then add n 1 new states (or none if u = ✏).
We’ll call them q2, q3,…,qn, but you don’t have to label them.
(b) Add transitions:
i. From qloop to qn, labelled ✏, A ! un
ii. For i = n 1, n 2,…, 2, from qi+1 to qi, labelled ✏, ✏ ! ui.
iii. From q2 to qloop, labelled ✏, ✏ ! u1.
We add a sequence of transitions which pop A from the stack and push
u on the stack in reverse order. When P returns to qloop, the current
word in the derivation will be read from the top of the stack to the bottom.
4. For each terminal a 2 ⌃, put an arrow from qloop to qloop labelled a, a ! ✏.
These match up the initial terminals of the current word with the next letters
of the input word w

Question 18

True/false: not all finite languages are regular

Answer 18

False; every finite language is regular.

Question 19

How does the pumping lemma change from regular languages to context-free languages?

Answer 19

You now break words into 5 parts, pumping the 2nd and 4th, instead of splitting it into 3 and only pumping the 2nd (middle) part.

Question 20

What is the pumping lemma for context-free languages?

Answer 20

Let L be a context-free language. Then there exists an integer N (the pumping length) such that, if w ∈ L and |w| > N, then w = uvxyz, where:

1. |vxy| < N,
2. |v| + |y| > 0,
3. for each i >= 0, the word uv^ i xy^ i z ∈ L.

Question 21

How do you use the pumping lemma for context-free languages?

Answer 21

??