Homework Two Solution– CSE 355

Due: 14 February 2012

Please note that there is more than one way to answer most of
these questions. The following only represents a sample solution.

Problem 1: Linz 3.1.21 and 3.2.18

3.1.21: Give a general method by which any regular expression r can be changed
into r̂ such that (L(r))R = L(r̂).
We will give a couple methods. The first uses only regular expressions (RE). The second convert the
regular expression to an NFA, finds the reverse and then converts that back into a regular expression.

Method 1. Given a RE, r, the following procedure rR will compute the reverse of r:

1. If r = ∅, then rR = ∅.

2. If r = λ, then rR = λ.

3. If r = a, then rR = a, for any a ∈ Σ.

4. If r = r1 + r2 , for REs r1 and r2 , then rR = r1R + r2R .

5. If r = r1 r2 , for REs r1 and r2 , then rR = r2R r2R .

6. If r = (r1 )∗ , for some RE r1 , then rR = (r1R )∗ .

Now we will show our procedure is correct. We will proceed by induction on the length of the
RE (You are not required to show induction on the homework, but should give and explanation
why the method would halt and why each part is correct).

• Base case: If |r| = 1, then r is one of the following forms:

1. r = ∅, then clearly rR = ∅.
2. r = λ, then clearly rR = λ.
3. r = a for some a ∈ Σ, then clearly rR = a.

• Induction Hypothesis: Assume for all |r| < n that (L(r))R = L(rR ).

• Now, let |r| = n > 1. Then r has one of the following forms:

1
 4. r = r1 + r2 , for REs r1 and r2 . Note that |r1 | < n and |r2 | < n. Now wR ∈ (L(r))R =
(L(r1 + r2 ))R = (L(r1 ) ∪ L(r2 ))R iff w ∈ L(r1 ) ∪ L(r2 ) iff w ∈ L(r1 ) or w ∈ L(r2 )
iff wR ∈ (L(r1 ))R or wR ∈ (L(r2 ))R iff wR ∈ L(r1R ) or wR ∈ L(r2R ) (by the I.H.) iff
wR ∈ L(r1R ) ∪ L(r2R ) iff wR ∈ L(r1R + r2R ) = L(rR ) by item 4 in the procedure above.
5. r = r1 r2 , for REs r1 and r2 . Note that |r1 | < n and |r2 | < n. Now wR = v R uR ∈
(L(r))R = (L(r1 r2 ))R = (L(r1 )L(r2 ))R iff w = uv ∈ L(r1 )L(r2 ) iff u ∈ L(r1 ) and
v ∈ L(r2 ) iff uR ∈ (L(r1 ))R and v R ∈ (L(r2 ))R iff uR ∈ L(r1R ) and v R ∈ L(r2R ) (by the
I.H.) iff wR = v R uR ∈ L(r2R )L(r1R ) iff wR ∈ L(r2R r1R ) = L(rR ) by item 5 in the procedure
above.
6. r = (r1 )∗ , for some RE r1 . Note that |r1 | < n. Now wR = w1R w2R . . . wnR ∈ (L(r))R =
(L(r1∗ ))R iff for all 1 ≤ i ≤ n, wiR ∈ (L(r1 ))R iff for all 1 ≤ i ≤ n, wiR ∈ L(r1R ) (by
the I.H.) iff wR = w1R w2R . . . wnR ∈ L(r1R )∗ = L(rR ) (by definition of *) by item 6 in the
procedure above.
• Since in every case the procedure produces the correct output, the procedure is correct. Also
note that the for any input r the procedure will terminate, since if |r| > 1 the procedure will
be applied recursively to shorter REs, until eventually |r| = 1 at which point the procedure
will terminate.
Method 2. Let r be a regular expression. Following the procedure given in Theorem 3.1 of
Linz, we convert r to an nfa, N , and then convert N to a dfa, D. Following the procedure given
in the solutions to 2.3.12 from HW1, convert D into an nfa, N R , such that L(N R ) = (L(D))R .
Lastly, follow the procedure nf a − to − rex given on page 83 of Linz, to convert L(N R ) into a RE,
r̂. From the conversions it is clear, (L(r))R = (L(N ))R = (L(D))R = L(N R ) = L(r̂).

3.2.18: Use the construction in Theorem 3.1 to find nfa’s for L(aφ) and L(φ∗ ). Is
the result consistent with the definition of these languages.
By Theorem 3.1, the nfa for L(a) can be represented schematically as shown below:

a
q0 q1

The nfa for L(∅) can represented as given below:

qφ0 qφ1

By Theorem 3.1, we can construct L(a∅) using concatenation of the above two nfa’s as shown
below:

2
 λ a λ λ
qs q0 q1 qφ0 qφ1 qf

a
q0 q1 q2

The concatenated nfa can be further simplified as shown above. Since this nfa has no path to the
final state q2 , the resulting language is L(∅). Also, we know that by definition, the concatenation
of any language with ∅ results in ∅. So the resulting nfa is consistent with the definition of the
language.
We already showed the construction of L(∅). By Theorem 3.1, we can construct L(∅∗ ) as shown
below:

λ λ
qs qφ0 qφ1 qf

Since this nfa has a path to the final state qf on λ, the resulting language is L(λ). Also, we know
that by definition, the star of any regular expression will result in a language which has at least one
element as λ and by definition, L(∅∗ ) is L(λ). So the resulting nfa is consistent with the definition
of the language.

Problem 2: Linz 3.3.6 and 3.3.14

3.3.6: Construct a right-linear grammar for the language L((aab∗ ab)∗ ).
A right-linear grammar is as follows:
S → A|λ
A → aaB
B → bB|abS

3
3.3.14: Show that for every regular language not containing λ there exists a right
linear grammar whose productions are restricted to the forms

A → aB,
or
A → a,
where A, B ∈ V , and a ∈ T .
In exercise problem 2.3.9, we proved that for any regular language L that does not contain λ, there
exists a nfa without λ-transitions and with a single final state that accept L. A new accept state
qf was added and for every state qi , if there is a transition from qi to a state in F on input a ∈ T ,
a transition from qi to qf on input a was added. Note that there were no outgoing transitions from
this single final state, qf . Also, every state in this nfa has a transition to some state in the nfa,
except for the single final state, since we created this nfa by converting a dfa with extra transitions
from qi to qf on input a for every state qi , if there was a transition from qi to a state in F on input
a ∈ T in the original dfa.
Now we can modify the proof for Theorem 3.4 to construct the right linear grammar for a regu-
lar language not containing λ, while accommodating the restrictions to the forms of productions as
mentioned above. Let M = (Q, T, δ, q0 , F ) be a dfa that accepts a regular language L not containing
λ. Let the corresponding nfa as detailed in the above construction be N = (Q ∪ {qf }, T, δ 0 , q0 , {qf })
where qf ∈ / Q. Here δ 0 can be represented in terms of δ as:

δ 0 (qi , a) = {qk } where δ(qi , a) = qk and qk ∈ / F,

δ 0 (qi , a) = {q ,
k fq } where δ(q i , a) = q k and q k ∈ F,

We assume that Q = {q0 , q1 , . . . , qn } and T = {a1 , a2 , . . . , am }. Construct the right-linear grammar

G = (V, T, S, P ) with

V = {q0 , q1 , . . . , qn }

and S = q0 . Note that qf ∈

/ V . For each transition

δ 0 (qi , aj ) = {qk } where δ(qi , aj ) = qk and qk ∈

/ F,

of N , we put in P the production

qi → a j qk

and for each transition

δ 0 (qi , aj ) = {qk , qf } where δ(qi , aj ) = qk and qk ∈ F ,

4
of N , we put in P the productions

qi → a j qk
qi → a j
We first show that G defined in this way can generate every string in L. Consider w ∈ L of the form

w = ai aj · · · ak al .
For N to accept this string, it must make moves via

δ 0 (q0 , ai ) = qp ,
δ 0 (qp , aj ) = qr ,
..
.
δ 0 (qs , ak ) = qt ,
δ 0 (q t , al ) = (qu , qf ), qu ∈ F .

By construction, the grammar will have one production for each of these δ 0 ’s. Therefore, we can
make the derivation

q0 ⇒ ai qp ⇒ ai aj qr ⇒∗ ai aj · · · ak qt
⇒ ai aj · · · ak al ,
with the grammar G, and w ∈ L(G). Conversely, if w ∈ L(G), then its derivation must have the
form shown above. But this implies that

δ 0∗ (q0 , ai aj · · · ak al ) = qf
Here note that the construction ensures the right linear grammar has productions restricted to the
forms

A → aB,
or
A → a,
where A, B ∈ V , and a ∈ T .

Problem 3: Linz 3.1.17

3.1.17: Write regular expressions for the following languages on {0, 1}.
(a): all strings ending in 01,
(0 + 1)∗ 01

5
(b): all strings not ending in 01,
(λ + 0 + 1 + (0 + 1)∗ (00 + 10 + 11))

(c): all strings containing an even number of 0’s,

(1∗ 01∗ 01∗ )∗

(d): all strings having at least two occurrences of the substring 00. (Note that with
the usual interpretation of a substring, 000 contains two such occurrences),
(0 + 1)∗ (00(0 + 1)∗ 00 + 000)(0 + 1)∗

(e): all strings with at most two occurrences of the substring 00,
(1 + 01)∗ (001+ (01+ )∗ 00 + 000 + 00 + 0 + λ)(1 + 10)∗

(f ): all strings not containing the substring 101.

0∗ 1∗ 0∗ + (1 + 00 + 000)∗ + (0+ 1+ 0+ )∗

Problem 4: Linz 3.2.5 and 3.2.9

3.2.5: Find dfa’s that accept the following languages.
(a) L = L(ab∗ a∗ ) ∪ L((ab)∗ ba).
A dfa for L is given by:

b
b
a a
a b
a,b
a
a,b
b
a a
b a b
a

b
a
b
b

6
(b) L = L(ab∗ a∗ ) ∩ L((ab)∗ ba).
Since any string in L must start with an a to be in L1 = L(ab∗ a∗ ), it must also start with an ab
or else it cannot be in L2 = L((ab)∗ ba). We cannot have a repeat of ab to be in L1 (after the first
b, if we get an a we cannot get any more b’s). Therfore to be in L2 the string must be abba. This
string is also in L1 . Thus, we see L = {abba}. A dfa for L is then given by:

a b b a

a a
b b b

a,b

3.2.9: What language is accepted by the following generalized transition graph?

a a+b a + b*

a a+b

a*b + c

The regular expression corresponding to the language can be represented by:

r = (a∗ a(a + b)∗ (a + b) + (a∗ b + c))(a + b∗ )∗

Problem 5: Linz 3.3.15

3.3.15: Show that any regular grammar G for which L(G) 6= ∅ must have at least
one production of the form
A→x
where A ∈ V and x ∈ T ∗ .
For a contradiction, assume that G = (V, T, S, P ) is regular with L(G) 6= ∅, but with no productions
of the form
A→x .

7
That means all productions in P are of the form

A → xB

for some A, B ∈ V and x ∈ T ∗ . Since L(G) 6= ∅, there must exist some w ∈ T ∗ such that w ∈ L(G).
That means there is some derivation S ⇒∗ w that ultimately terminates after producing w, which
means there is some step in the derivation which does not produce a variable. However, this
contradicts our assumption that all productions are of the form

A → xB.

Thus, we conclude that at least one production in P is of the form

A→x .