CS481F01 Solutions 4 – CFGs

A. Demers

10 Oct – due 17 Oct

1. For each of the following languages, give a context-free grammar that gen-
erates the language.

(a) { 0i 1i | i ≥ 0 }∗
(b) { 0i 1j 0k | i = j ∨ j = k }
(c) { 0i 1j | i ≤ j ≤ 2i }
(d) { w ∈ {0, 1}∗ | ]1(w) = ]0(w) }
(e) { x ∈ {0, 1}∗ | ¬( (∃i, j)(x = (0i 1i )j ) ) }

(answer a) We start with the productions

S → AS | 

It is straightforward to argue that (in the absence of any other productions for
S) L(S) = L(A)∗ . Then add

A → 0A1 | 

to generate the strings 0i 1i and we’re done.

(answer b) This is the union of two sets:

{ 0i 1i 0k | i, k ≥ 0 } ∪ { 0i 1k 0k | i, k ≥ 0 }

and can be generated by

S → AC | CB
A → 0A1 | 
B → 1B0 | 
C → 0C | 

1
Note this grammar is ambiguous: any string of the form 0i 1i 0i is generated in
two different ways, one way using A and the other using B. It can be shown
that this property is necessary. The language is inherently ambiguous – that is,
every grammar generating the language is ambiguous.

(answer c) Here is an ambiguous grammar:

S → 0SA | 
A → 1 | 11

This language is not inherently ambiguous, however. The following unambigu-

ous language also generates it:

S → 0S11 | A
A → 0A1 | 

To argue correctness, argue that either grammar generates a subset of 0∗ 1∗ and

every production that generates a 0 generates either one or two 1s.

(answer d) There are many similar answers. Suppose G has productions

S → 0S1S | 1S0S | 

Clearly every generated string has equal numbers of 0s and 1s, since every rule
that generates a 0 also generates a 1 and vice versa. Can all such strings be
generated by G? We can argue by induction on the string length. Clearly G
generates . For nonempty strings, suppose the string starts with 0. Write it
0x. Then

]1(x) = ]0(x) + 1

Consider the shortest prefix of x for which this property holds. At least one
such prefix must exist, since the property holds of x, which is a prefix of it-
self. Moreover, the shortest such prefix necessarily ends with 1, and the part
preceding the 1 has equal numbers of 0s and 1s; that is:

x = y1z where ]1(y) = ]0(y)

Now, by subtraction

]1(y1z) = ]0(y1x) + 1 ⇒ ]1(z) = ]0(z)

2
The induction hypothesis applies to both y and z, allowing us to conclude that

S → 0S1S →∗ 0y1S →∗ 0y1z

which is what we wanted. The case where the string starts with 1 is completely
symmetric.

(answer e) This one is a bit tricky. Let

L̄ = { x | (∃i, j)(x = (0i 1i )j ) ) }

That is, L̄ is the set of “bad” strings. How can a string fail to be bad? Note
first that every w ∈ {0, 1}∗ trivially consists of alternating sequences of 0s and
1s. To be bad, a string must

1. start with a 0,

2. end with a 1,

3. have m = n in each 0m 1n sequence,

4. have m = n in each 1m 0n sequence.

Claim these four properties completely characterize the bad strings; the good
strings (the strings in L) are strings that violate any one of the properties.
Generating strings that violate the properties by a CFG is comparatively easy.
First, introduce productions

A → 0A | 1A | 

Clearly A generates any string in {0, 1}∗ .

To violate property (1), just add

S → 1A

to generate all strings that do not begin with 0.

Similarly, to violate property (2) we add

S → A0

which generates all strings that do not end with 1.

3
To violate property (3), we first add productions

B → 0B1 | 0C1 | 0D1

C → 0C | 0
D → D1 | 1

B generates

{ 0m 1n | m, n > 0 ∧ m 6= n }

Now we can violate property (3) with the productions

E → A1 | 
F → 0A | 
S → EBF

where E and F are used to construct left and right context for the (maximal)
sequence from 0∗ 1∗ generated by B.
Violating property (4) is completely analogous. We add productions

G → 1G0 | 1H0 | 1J0

H → 1H | 1
J → J0 | 0

so G generates

{ 1m 0n | m, n > 0 ∧ m 6= n }

Now we can violate property (4) with the single production

S → A0G1A

Note that the left and right context for G are somewhat simpler than the context
for B. We assume to violate (4) an instance of G must be surrounded by 0G1;
the case where G appears at either end of the string is already covered by
properties (1) and (2).

2. Recall from lecture that a right linear grammar is one in which the produc-
tions are of the form
S → ε
A → aB or
A → a

These grammars are often called regular grammars. In this question you show
why.

4
(a) Suppose you are given an arbitrary union-dot-star regular expression E.
Show (by induction on the structure of E) how to construct a right linear gram-
mar G such that L(G) = L(E). Explain your answer.

(answer a) As announced in lecture, you may answer this problem using 

rules in your right linear grammars for “nearly full credit.” For full credit, you
can observe that the construction from the text and lectures for eliminating
chain rules and  rules converts a right-linear grammar with  rules to a right-
linear grammar without  rules. Specifically, suppose L is generated by grammar
G whose productions have the form

A → aB or A → 

We close the set of productions under the rule

A → aB ∧ B →  ⇒ A → a

We then eliminate all  rules. The resulting grammar is right-linear and gen-
erates L − {}. To restore  to the language if necessary, we add a new start
symbol S 0 with the productions

S0 → α if S → α
S0 →  if  ∈ L

Thus, to show that the strict right linear grammars can generate any regular
set, it is sufficient to show that right linear grammars with  rules can generate
any regular set. That’s what we’ll do here, since it’s easy.
We give an inductive construction on the regular expression E.
Case 1 (E = a): The productions

S → aA A → 

are sufficient, and give us a right-linear grammar with  rules as described above.
Case 2 (E1 + E2 ): Assume we have constructed grammars

Gi = ( Ni , Σ, Pi , Si ) for Ei

We merge the sets of productions and add

S → α for α where S1 → α ∨ S2 → α

5
This grammar correctly generates the union, and all productions are of the
proper form.
Case 3 (E1 · E2 ): Here we can rely on the assumption that the grammar uses
epsilon rules. We merge the grammars G1 and G2 ; then let

S → α for α where S1 → α

Then for every production A →  in G1 we remove that production and replace

it by the set

A → α for α where S2 → α

The fact that this grammar generates the concatenation of L(E1 ) and L(E1 )
follows from the fact that every derivation in G1 ends by replacing the rightmost
symbol (a nonterminal) by .
Case 4 (E1∗ ): This case looks a lot like concatenation. We add a new start
symbol S with the productions

S → 
S → α for α where S1 → α

Now, for every production A →  in G1 we add the set

A → α for α where S1 → α

Note we do not remove the production A → .

This constructs a right-linear grammar with  rules for any regular expression.
The conversion procedure given above can be used to construct a right-linear
grammar without  rules if required.

(b) Suppose you are given an arbitrary right linear grammar G. Show how
to construct an NFA M such that L(M ) = L(G). Argue that your solution is
correct.

(answer b) Given a right-linear grammar without  rules

G = ( N, Σ, P, S )

6
We construct NDFA

M = ( Q, Σ, ∆, SM , F )

as follows. First, the states are

Q = N ∪ {f }

where f is a new state name different from any symbol of N . The transition
function is

∆(A, a) = { B | A → aB ∈ P } ∪ { f | A → a ∈ P }

The start and final states are

SM = { S }
F = {f } ∪ {S |S→ ∈ P }

This requires a (fairly routine) inductive proof that the states of the machine
correspond to the nonterminals used in a derivation. Specifically,

ˆ
B ∈ ∆(A, w) iff A →∗ wB
ˆ
f ∈ ∆(A, w) iff A →∗ w (w 6= )
S ∈ F iff S →  iff ˆ
∆(S, ) ∈ F

from which the equivalence of the languages follows.

3. Say grammar G is a symmetric linear grammar if its productions are of the

form

A → aBc
A → a or
A → 

A language L is a symmetric linear language if L = L(G) for some symmetric

linear grammar G.

(a) Give an example of a symmetric linear language that is not regular.

(answer a) Our old friend {0i 1i | i ≥ 0} will do.

7
(b) Prove every regular language is a symmetric linear language. For exam-
ple, given a DFA M , show how to construct a symmetric linear grammar G
generating L(M ).

(answer b) Okay, this is a bit subtle, but similar to some of the “first half”
constructions we did for finite automata, and very similar to the proof given in
lecture that CFLs are closed under intersection with regular sets. Given a DFA

M = ( Q, Σ, δ, s, F )

we will construct an equivalent symmetric linear grammar

G = ( N, Σ, P, S }

where

N = { S } ∪ (Q × Q)

We denote nonterminals from Q × Q using square brackets, e.g. [pq]. Now the
productions of G are

S →  if s ∈ F
S → a if δ(s, a) ∈ F
S → a[pq]b if δ(s, a) = p ∧ δ(q, b) ∈ F

[pq] →  if p = q
[pq] → a if δ(p, a) = q
0 0
[pq] → a[p q ]b if δ(p, a) = p0 ∧ δ(q 0 , b) = q

Correctness follows from a routine inductive proof of the claims

[pq] →∗ w ⇔ δ̂(p, w) = q
S →∗ w ⇔ (∃f ∈ F )δ̂(s, w) = f

(c) Show that every symmetric linear language over a single-letter alphabet is
regular.

8
(answer c) Gosh, over a single-letter alphabet, the order of the symbols
doesn’t matter. Given a symmetric linear grammar over the alphabet {0}, we
transform the productions as follows

A → 0B0 becomes A → 00B

A→0 unchanged
A→ unchanged

Over a single letter alphabet the generated language is unchanged. But the
new grammar is (or is trivially convertible to) a right-linear grammar, and so
generates a regular set.