Problem 1:
Show that the language L = {w ∈ {a, b, c}∗
: na(w) + nb(w) = nc(w)} is context-free, but not linear.
In order to show that the language is context-free, we will give the corresponding NPDA.
Define M = ({q0, q1}, Σ, {a, c, z}, δ, q0, z, {q1}) with
δ(q0, a, z) = {(q0, az)}, δ(q0, a, a) = {(q0, aa)}, δ(q0, a, c) = {(q0, λ)},
δ(q0, b, z) = {(q0, az)}, δ(q0, b, a) = {(q0, aa)}, δ(q0, b, c) = {(q0, λ)},
δ(q0, c, z) = {(q0, cz)}, δ(q0, c, a) = {(q0, λ)}, δ(q0, c, c) = {(q0, cc)},
δ(q0, λ, z) = {(q1, λ)}.
Then M accepts L since it keeps count of how many a’s and b’s are read with the stack symbol a and how many c’s
with the symbol c. For each a and b seen it will cancel a c if that is on the top of the stack or add an a. Similarly, for
each c seen, it will add a c to the stack or cancel an a if it is on top of the stack. Finally, we only accept if the number
of c’s is the same as the number of a’s and b’s combined, that is they all cancel each other on the stack.
To show that the language is not linear, we will use the pumping lemma for linear language. Assume that the
language is linear and apply the PL to the string w = amc
2mb
m.
|uvyz| ≤ m shows that in this case the strings u, v must both consist entirely of a’s, that is v = ak1 and y, z must both
consist entirely of b’s, that is y = bk2. If we pump this string once, we get am+k1
c
2mb
m+k2
, with either k1 ≥ 1 or k2 ≥ 1, a
result that is not in L. This is a contradiction, it proves that the language is not linear.
Problem 2:
Show that the family of context-free languages is not closed under difference in general, but is closed under regular
difference, that is, if L1 is context-free and L2 is regular, then L1 − L2 is context-free.
To show that context free languages are not closed under difference in general, we will give two context free
languages whose difference is no longer context free. Let L1 = {an b
n
c
m |m, n ≥ 0} and L2 = {𝑎𝑚𝑏
𝑛𝑐 ̅̅̅̅̅̅̅̅̅̅𝑛̅ | m, n ≥ 0}. L1
and L2 are both context free languages (in fact deterministic context free languages),
which is not context free as stated in class. Thus, the family of context free languages is not closed under
difference.
Next, we will show that the class of context free languages is closed under regular difference. Let L1 be any context
free language and L2 be any regular language. We know that regular languages are closed under complement,
therefore L2 is a regular language. We also know that context free languages are closed under regular intersection.
Thus, L = L1 − L2 = L1 ∩ 𝐿2
̅̅̅ is a result of a regular intersection and is therefore a context free language.
Problem 3:
Design Turing machines to compute the function for x and y positive integers represented in unary. For each of
these problems let u(x) = 1x where 1x
is 1 concatenated with itself x times.
We will assume that u(0) = λ and will be represented by the tape having only blanks on it.
(a) 𝑓(𝑥) = 3 𝑥.
The input to our tape will be u(x) and the output will be u(3x). We will first mark all the 1’s and then for
every marked 1 we see we will write two 1’s at the end of the string, thus tripling the string. We will define
the TM as follows:
States Q = {q0, q1, q2, q3, qf}, where q0 is the start state and qf the only final state,
Input symbols Σ = {1},
The input to our tape will be u(x) − u(y) and the output will be u(x − y) if x > y and the blank tape otherwise.
One strategy will be to remove a 1 from the end of the string (the y portion) and then remove a
corresponding 1 from the front of the string (the x portion). We continue until either we are out of 1’s in
the y portion, in which case we have u(x − y) on the tape, or we are out of 1’s in the x portion in which case
x ≤ y, so we clear the tape and halt with the blank tape.
c) 𝑓(𝑥, 𝑦) = 2𝑥 + 3𝑦
The input to the tape will be u(x) + u(y) and the output will be u(2x + 3y). We will first mark all the 1’s
before the plus with one dot and then change the plus to a one with two dots and continue marking every
one after it with two dots. We will remove the last 1 as extra to the sum. Then for every 1 with two dots
seen we will write two 1’s and the end of the string and for every 1 with one dot we will write one 1 and
the end of the string, yielding the required total. Our strategy is to mark a 1 at the start of
the string and remove a corresponding one at the end of the string. We will repeat marking the next
unmarked 1 at the beginning and removing another 1 at the end. We will continue until there is no
unmarked 1 left (x was even) and we cut the output in half, or there is no one left to remove at the end (x
was odd) and the output is the fraction rounded up. Then we clear all marks and halt.
e) 𝑓(𝑥) = 𝑥 𝑚𝑜𝑑 5
The input to the tape will be u(x) and the output will be u(x mod 5). Our strategy is to mark all the 1’s as we
scan to the right using our states to remember how many 1’s we have seen mod 5. Then we will remove
the marks from that many 1’s and scan back to the left over the remaining marked 1’s. Then we will delete
all the marked ones and halt with x mod 5 on the tape.
Problem 4:
Let L be a deterministic context-free language and define a new language L1 = {w| aw ∈ L, a ∈ Σ}. Is it necessarily
true that L1 is a deterministic context free language?
No! Let’s give a counter-example. Let L = {c an b
n
| n ≥ 0} ∪ {d an b 2n | n ≥ 0}, then L is a deterministic context free
language, if we start with a c we follow a branch where we accept or if we read an a we push one extra a on the
stack and then pop one a for each b read, accepting only if the stack is empty. If we start with a d, then we follow
another branch where we accept or if we read an a we push two extra a’s on the stack and then for each b rea d we
pop one a, accepting only if the stack is empty. In every configuration we can only move to one other configuration,
meeting the criteria for determinism. However, then L1 = {an b
n
| n ≥ 0} ∪ {a
n b
2n | n ≥ 0} (removing the first symbol
from every string in L), which is the language in Example 7.11 (Peter Liz 3rd ed.) which was shown in the example to
be nondeterministic.
Problem 5:
Transform the grammar with productions S → abAB, A → baB|λ, B → BAa|A|λ. into Chomsky normal form.
Removing λ−productions:
Here A and B are nullable variables, we get
S → abAB|abA|abB|ab, A → baB|ba, B → BAa|A|Ba|Aa|a.
Removing unit-productions:
S → abAB|abA|abB|ab, A → baB|ba, B → BAa|baB|ba|Ba|Aa|a.
There are no useless productions in the grammar.
Now, we introduce variables C and D to substitute terminals a and b.
S → CDAB|CDA|CDB|CD, A → DCB|DC,
B → BAC|DCB|DC|BC|AC|a, C → a, D → b.
Finally, we introduce variables to shorten the right sides of the production.
S → EF|EA|EB|CD A → GB|DC, B → BH|GB|DC|BC|AC|a,
E → CD, F → AB, G → DC, H → AC, C → a, D → b.
Problem 6:
Construct an NPDA corresponding to the grammar S → aABB|aAA, A → aBB|a, B → bBB|A.
The grammar does not have any λ−productions. So, we can convert it into Greibach normal form. Get rid of the unit
production,
S → aABB|aAA, A → aBB|a, B → bBB|aBB|a.
Define M = ({q0, q1, qf }, Σ, {S, A, B, z}, δ, q0, z, {qf }) with
δ(q0, λ, z) = {(q1, Sz)}, δ(q1, a, S) = {(q1, ABB),(q1, AA)},
δ(q1, a, A) = {(q1, BB),(q1, λ)}, δ(q1, b, B) = {(q1, BB)},
δ(q1, a, B) = {(q1, BB),(q1, λ)}, δ(q1, λ, z) = {(qf , z)}
Problem 7:
Is it possible for a regular grammar to be ambiguous?
Yes. Consider the grammar
S → A|λ A → λ.
Then there are two leftmost derivations that generate the string λ. The first is S ⇒ λ and the second is S ⇒ A ⇒ λ.
Thus, this regular grammar is ambiguous. Regular grammars cannot be inherently ambiguous.
Problem 8:
Eliminate useless productions from S → a|aA|B|C, A → aB|λ, B → Aa, C → cCD, D → ddd.
Following the algorithm given in the proof of Theorem 6.2 (3rd edition), we will first remove productions that
cannot generate any strings. Let V1 = ∅. Since S → a, A → λ and D → ddd are productions we add S, A and D to V1.
Then, since B → Aa is a production we add B to V1. There are no more variables that can produce a string following
the algorithm. Removing these useless productions yields the grammar
S → a|aA|B, A → aB|λ, B → Aa, D → ddd.
Next, we remove the unreachable variables. We will start with V2 = {S} since S is the start variable, we always reach
it. We can reach the variables A and B from S so they are added to V2. A and B can only reach each other so our
algorithm terminates. Since D is not in V2 it cannot be reached by any derivation of this grammar. Therefore, we
remove all productions with D, yielding the final grammar free of useless productions and useless variables.
S → a|aA|B, A → aB|λ, B → Aa,
Problem 8:
Construct NPDA that accept the following language on Σ = {a, b, c}. (a) L = {an b
2n | n ≥ 0}.
Define M = ({q0, q1, q2, q3}, Σ, {a, z}, δ, q0, z, {q0, q3})
with δ(q0, a, z) = {(q1, aaz)}, δ(q1, a, a) = {(q1, aaa)},
δ(q1, b, a) = {(q2, λ)}, δ(q2, b, a) = {(q2, λ)}, δ(q2, λ, z) = {(q3, λ)}.
Then M accepts L since it accepts the empty string and for each a seen it pushes two additional a’s onto the stack (3
total). Then it pops one a for each b seen guaranteeing there are twice as many b’s as a’s. Finally, it accepts if the
input is done and there are no more a’s on the stack.