Context-Free Languages

Context-Free Languages

(Reference: Chapter 3 of Maheshwari & Smid)

University of New Brunswick

CS2333: Computability and Formal Languages

1 Context-Free Languages
Context-Free Languages

Context-Free Grammars

I Regular Expressions: provided a way to describe regular

languages

I Context-Free Grammars (CFGs): provide a way to describe

languages called context-free languages
I Context-free grammars can be very useful for describing the
syntax of programming languages (used in compilers).

I To be shown later: All regular languages are context-free, but

there are context-free languages that are not regular.
[Diagram on the board]

2 Context-Free Languages
Context-Free Languages

CFG example

I A simple CFG example:

I Substitution rules (or productions) are used to generate the

strings in the language

S → AB
A → 0A
A→0
B → 1B
B→1

I S, A and B are variables (S is the start variable), and 0 and 1

are terminals.

3 Context-Free Languages
Context-Free Languages

CFG example (continued)

I Note: Usually, we combine multiple rules with the same

variable on the left-hand side into one rule, so our example on
the previous slide becomes:

S → AB
A → 0A | 0
B → 1B | 1

4 Context-Free Languages
Context-Free Languages

Using context-free grammars

I A context-free grammar is used to derive strings of terminals

as follows:
I Start with the start variable (S in our example).
I Repeat the following until only terminals remain:
I Replace any variable in the current string with the right-hand
side of a rule for that variable.

I Example:
S ⇒ AB ⇒ 0AB ⇒ 0A1B ⇒ 001B ⇒ 0011B ⇒ 00111

I Such a derivation can also be represented in a parse tree

(shown on the board)

5 Context-Free Languages
Context-Free Languages

The language of a grammar

I For a context-free grammar G , the language of G , denoted

L(G ), is the set of all strings of terminals that can be derived
from the start variable.

I For our example grammar, the language generated is:

{0i 1j | i ≥ 1, j ≥ 1}

I Any language that can be generated by some context-free

grammar is a context-free language.

I More examples on the board

6 Context-Free Languages
Context-Free Languages

Formal definition of a CFG

I A context-free grammar is a 4-tuple G = (V , Σ, R, S) where:

I V is a finite set of variables
I Σ is a finite set of terminals
I V ∩Σ=∅

I S ∈ V is called the start variable

I R is a finite set of rules of the form A → w , where A ∈ V and
w ∈ (V ∪ Σ)∗

7 Context-Free Languages
Context-Free Languages

Some strategies for designing CFGs

I CFGs can be harder for people to come up with than finite

automata and regular expressions.

I The suggestions on the following slides might be helpful in

certain cases.

8 Context-Free Languages
Context-Free Languages

Strategy #1

I Sometimes, a context-free language (CFL) is the union or

concatenation of simpler CFLs.

I In this case, break it down into simpler grammars with start

variables S1 , S2 , · · · , Sk and then combine all the rules, plus a
first rule:
I S → S1 | S2 | · · · | Sk in the case of union

I S → S1 S2 · · · Sk in the case of concatenation

I Examples on the board

9 Context-Free Languages
Context-Free Languages

Strategy #2

I Often, strings in a CFL have two parts where we need to

remember a possibly infinite amount of information about one
part in order to make sure it matches with the other part.

I Example: {0n 1n | n ≥ 0}

I Use the rule R → 0R1

(every 0 at the beginning must be matched by a 1 at the end)

I In general: R → uRv (where there is some connection

between u and v )

10 Context-Free Languages
Context-Free Languages

Strategy #3

I Many CFLs have a recursive nature to them.

I One of our earlier examples: L = even-length palindromes

over {0, 1}

I What is an even-length palindrome? It’s either:

I 0x0 where x is an even-length palindrome,
I or 1y 1 where y is an even-length palindrome,
I or ε.

I So, a grammar is S → 0S0 | 1S1 | ε

11 Context-Free Languages
Context-Free Languages

Strategy #4

I If we recognize that a particular CFL happens to be a regular

language as well, we can construct a DFA and then convert it
to a CFG, as follows:

I For each state qi in the DFA, make a variable Vi .

I Add the rule Vi → aVj if δ(qi , a) = qj

I Add the rule Vi → ε if qi is an accepting state

I Make V0 the start variable where q0 is the start state.

I Example on the board

12 Context-Free Languages
Context-Free Languages

Designing CFGs

I Several more examples on the board

13 Context-Free Languages
Context-Free Languages

Chomsky Normal Form

I Sometimes, we want all the rules of a CFG to be in a

particular format. (More on why later in the course)

I One of the simplest forms:

Chomsky Normal Form (CNF) → useful for parsing
programming languages

I A CFG is in Chomsky Normal Form if every rule is of one of

the forms:
A → BC or A→a
where a is a terminal, and where A, B, C are variables (B, C
are not the start variable)

I Also allowed: S → ε if S is the start variable

14 Context-Free Languages
Context-Free Languages

Chomsky Normal Form (continued)

I It turns out that any CFG can be converted to an equivalent

CFG in Chomsky Normal Form.

I There are several steps in the conversion technique, covered

on the next few slides.

15 Context-Free Languages
Context-Free Languages

Conversion to Chomsky Normal Form

I Step 1: If the start variable S appears on the right side of

any rule in the grammar, then create a new start variable S1
and a new rule S1 → S

16 Context-Free Languages
Context-Free Languages

Conversion to Chomsky Normal Form

I Step 2: Eliminate all ε-rules (except possibly for S1 → ε)...

I For each ε-rule in the grammar (A → ε):

I Eliminate the rule A → ε from the grammar.
I Then, for every rule in the grammar of the form B → α, where
the variable A appears at least once in the right side α, add
new rules with every combination of removing one or more
instances of A from α (basically replacing A with ε)
I For example, if there is a rule B → 0ACA1, we would also add
the new rules B → 0CA1, B → 0AC 1 and B → 0C 1

(The only exception is that we should not add the rule B → ε

if we had already removed that ε-rule earlier.)

17 Context-Free Languages
Context-Free Languages

Conversion to Chomsky Normal Form

I Step 3: Eliminate all unit rules...

I For every rule of the form A → B (where A and B are

variables),
I Eliminate the rule A → B.

I For every rule of the form B → α, add a new rule A → α

(unless this creates a unit rule that was already eliminated
earlier).
I For example, if we eliminated the rule X → Y , and the
grammar already contained the rules
Y → 0Z , Y → 1 and Y → PQR,
then we would add the new rules
X → 0Z , X → 1 and X → PQR

18 Context-Free Languages
Context-Free Languages

Conversion to Chomsky Normal Form

I Step 4: Eliminate all rules that have more than two symbols
on the right side...

I For every rule of the form A → u1 u2 u3 · · · uk where all the ui

are variables or terminals, replace that rule with the rules
A → u1 A1
A1 → u2 A2
A2 → u3 A3
..
.
Ak−3 → uk2 Ak−2
Ak−2 → uk−1 uk
where A1 , A2 , · · · Ak−2 are new variables
I For example, the rule A → 0B1CD could be replaced by the
rules A → 0X , X → BY , Y → 1Z , Z → CD
19 Context-Free Languages
Context-Free Languages

Conversion to Chomsky Normal Form

I Step 5: Eliminate all rules of the form A → u1 u2 where at

least one of u1 , u2 is not a variable...
I If u1 and u2 are both terminals, then replace the rule
A → u1 u2 with A → U1 U2 , U1 → u1 and U2 → u2 ,
where U1 and U2 are new variables.

I If only u1 is a terminal, then replace the rule A → u1 u2 with

A → U1 u2 and U1 → u1 , where U1 is a new variable.

I If only u2 is a terminal, then replace the rule A → u1 u2 with

A → u1 U2 and U2 → u2 , where U2 is a new variable.

20 Context-Free Languages
Context-Free Languages

Conversion to Chomsky Normal Form

I Step 5 (continued): Eliminate all rules of the form

A → u1 u2 where at least one of u1 , u2 is not a variable...

I For example, if we have the rule A → 01, we can replace it by

A → XY , X → 0 and Y → 1.
If we also have the rule A → 0Z , then we could replace it by
A → WZ and W → 0.
(However, if we had already created X → 0 in a previous step,
then there is no need to add a new variable like W . We can
just create the rule A → XZ (and X → 0 already exists).

21 Context-Free Languages
Context-Free Languages

Pushdown automata

I Just as finite automata were used to accept regular languages,

we can use machines called pushdown automata (PDAs) to
accept context-free languages.

I If L is a context-free language, then we can create a PDA that

will accept all strings that are in L and reject all strings that
are not in L.

I Note: The model that we use for PDAs will be different from
the one in the book, but both models are equivalent.

22 Context-Free Languages
Context-Free Languages

Example
I Discussed earlier: there is no FA that will accept the language
L = {0n 1n : n ∈ Znonneg }

I We proved this using the Pumping Lemma, but the intuitive

idea was that we would need an infinite number of states to
keep track of whether any arbitrary string was in L or not.

I However, what if our FA also had access to an infinitely large

stack?

I We can push symbols onto the stack and pop symbols off the
stack. This provides us with an ability to remember more than
we can remember with just states alone.

I This is the basic idea of a PDA: a finite automaton + a stack

23 Context-Free Languages
Context-Free Languages

How a PDA works

I Given an input string w :

I Start in an initial state q0 with only a special symbol $ on the
stack. (We will discuss the purpose of $ later.)

I As we read the individual symbols of w , we move between

states and modify the contents of the stack, according to a
transition function δ.
I Depending on the current state r , the current input symbol a
being read, and the symbol X popped from the top of the
stack, the PDA moves to a state r 0 and replaces X on the
stack with a string of symbols α

I If there is any sequence of moves taking us from q to any

accepting state after reading all symbols in w , then w is
accepted. (By default, PDAs are nondeterministic.)

24 Context-Free Languages
Context-Free Languages

State diagrams for PDAs

I Our state diagrams will be the same for PDAs as they were
for FAs, but we must show not only what input symbol is
read, but what is happening with the stack.

I Each transition is labelled with the input symbol being read,

the symbol found at the top of the stack when it is popped,
and what (if anything) is to be pushed onto the stack.

I (Example transition shown on the board)

25 Context-Free Languages
Context-Free Languages

Example (from earlier)

I Idea behind a PDA for L = {0n 1n : n ∈ Znonneg }
I As we read zeroes in the input string, push each zero onto the
stack.
I Once we start seeing ones in the input string, we want to
ensure that the number of ones equals the number of zeroes:
I Every time a one occurs in the string, pop a zero from the
stack (to match it).
I Once we have started seeing ones in the string, if we ever see
another zero, then reject the string.
I If we ever see a one, but there is no matching zero left on the
stack, then reject.
I If we reach the end of the string and the stack still contains
zeroes, then reject.
I We only accept if we reach the end of the string and the
zeroes have been emptied from the stack (i.e., the last one
matched the first zero that was pushed on).

26 Context-Free Languages
Context-Free Languages

State diagram for our example

I Two different versions of a state diagram for our 0n 1n

example (on the board)

27 Context-Free Languages
Context-Free Languages

Formal definition of a PDA

I A pushdown automaton is a 6-tuple M = (Q, Σ, Γ, δ, q0 , F ),

where
I Q is a finite set of states

I Σ is a finite input alphabet

I Γ is a finite stack alphabet, which contains a special symbol $

I δ is the transition function

δ : Q × (Σ ∪ {ε}) × (Γ ∪ {ε}) → P(Q × Γ∗ )
(See next slide)
I q0 ∈ Q is the start state

I F ⊆ Q is the set of accept states

28 Context-Free Languages
Context-Free Languages

Formal definition (continued)

I The transition function
δ : Q × (Σ ∪ {ε}) × (Γ ∪ {ε}) → P(Q × Γ∗ ) is the
“program” for the PDA and specifies what can be done in one
computation step.
I δ(r , a, X ) is the set of moves that can be made when we:
I are in state r
I read input symbol a (which can be ε, meaning that we can
make a move without reading a symbol from the input string)
I pop symbol X from the top of the stack (X can be ε,
meaning that we don’t pop anything from the stack)

I Each move in δ(r , a, X ) specifies:

I a next state r 0
I a string α (possibly empty) to be pushed onto the stack
(left end of α is the top, so pushing 012 indicates that we
push 2, then 1, then 0)
29 Context-Free Languages
Context-Free Languages

More PDA examples

I (More PDA examples on the board)

30 Context-Free Languages
Context-Free Languages

Deterministic vs. nondeterministic PDAs

I Note: Our PDA definition included nondeterminism. The

current computation step can be a choice of zero or more
possible moves for a given (state, input symbol, stack symbol)
combination.

I A string is accepted if there is any sequence of moves that

leads to an accepting state. Otherwise, the string is rejected.

I A deterministic PDA is one for which there is always exactly

one possible move.

31 Context-Free Languages
Context-Free Languages

Deterministic vs. nondeterministic PDAs

I For finite automata, we learned that anything that can be

done with a nondeterministic FA can also be done with a
deterministic FA. The two models are equivalent in power.

I Is this also the case for PDAs?

I It turns out that the answer is no.

I For instance, the example

L = {vbw : v ∈ {a, b}∗ , w = {a, b}∗ , |v | = |w |}
cannot be accepted by any deterministic PDA.

I Nondeterministic PDAs and deterministic PDAs are not

equivalent in power.

32 Context-Free Languages
Context-Free Languages

PDAs and CFGs

I Theorem: A language A is context-free if and only if there is

a nondeterministic pushdown automaton that accepts A.

I Proof: See Section 3.7 of the textbook. (You are not

responsible for knowing this proof.)

33 Context-Free Languages
Context-Free Languages

Non-context-free languages

I Pushdown automata are more powerful than finite automata,

but they are still limited.
I One of the main limitations is that we can only go through the
string once from left to right. Once we have read a particular
symbol in the string, we cannot visit that symbol again.

I What types of languages are not context-free?

I One example is L = {an b n c n : n ≥ 0}

I How do we prove that L is not context-free?

34 Context-Free Languages
Context-Free Languages

Proving that languages are not context-free

I To prove that a language is not context-free, we can use a

variation on the Pumping Lemma.

I The basic idea is the same as what we saw in Chapter 2.

I The Pumping Lemma for Context-Free Languages states

that all context-free languages have a certain property.

I If we can prove that some language L does not have that

property, then it must not be context-free.

I The details of the Pumping Lemma for Context-Free

Languages are slightly more complicated than for regular
languages, and proofs often have to be broken into two or
more cases, but the general idea is the same.

35 Context-Free Languages
Context-Free Languages

Pumping Lemma for Context-Free Languages

If A is a context-free language, then there is an integer p ≥ 1

(the pumping length) such that the following holds:
Every string s ∈ A, with |s| ≥ p, can be divided into five
pieces, s = uvxyz, satisfying:
1. |vy | ≥ 1 (i.e., v and y are not both empty)

2. |vxy | ≤ p

3. ∀i ≥ 0, uv i xy i z ∈ A

36 Context-Free Languages