HW2 Solutions 2016 Spring

Introduction to Formal Language, Fall 2016 Due: 22-Mar-2016
Homework 2 Solutions
Instructor: Prof. Wen-Guey Tzeng Scribe: Amir Rezapour Yi-Ruei Chen
1. Find all strings in L((a + b) b(a + ab) ) of length less than four.
Answer.
The strings with length 1: {b} = {b};
The strings with length 2: {ab, bb, ba} = {ab, bb, ba};
The strings with length 3: {(aa)b, (ab)b, (ba)b, (bb)b, (a)b(a), (b)b(a), b(ab)} =
{aab, abb, bab, bbb, aba, bba, bab}. 2
2. Find a regular expression for the set {an bm : (n + m) is even}.

Answer.
There are two cases:
n and m are even: (aa) (bb );

n and m are odd: a(aa) b(bb );
Thus, a regular expression for the set {an bm : (n + m) is even} is (aa) (bb ) +
a(aa) b(bb ). 2
3. Give a regular expression for L = {an bm : n < 4, m 3}.

Answer.
A regular expression for L1 = {an : n < 4} is + a + aa + aaa;
A regular expression for L2 = {bm : m 3} is + b + bb + bbb;
Thus, a regular expression for L = L1 L2 is ( + a + aa + aaa)( + b + bb + bbb). 2
4. What languages do the expressions ( ) and a denote?

Answer.
L(( ) ) = (L( )) = ( ) = {};
L(a) = L(a)L() = {a}{} = . 2
5. Find a regular expression for L = {vwv : v, w {a, b} , |v| 3}.

Answer.
For any string x {a, b} , we can treat it as x = x, where v = , x = w. Therefore,
any string x {a, b} is in L. Thus, L = (a + b) . 2
6. Give a regular expression for all strings that contain no run of as of length greater
than two. ( = {a, b, c}).
Answer.
1
A regular expression for {an : n 2} is + a + aa.
Thus, for = {a, b, c}, a regular expression for all strings that contain no run of as
of length greater than two is (( + a + aa)(b + c)) ( + a + aa). 2
7. Give a regular expression for all strings with at most two occurrences of the substring
00. ( = {0, 1}).
Answer.
There are three cases for a string with at most two occurrences of 00:
0 occurrence of 00: ;
1 occurrence 00: 00;
2 occurrences 00: 000, 0011 00;
Thus, a regular expression for all strings with at most two occurrences of the substring
00 is (1 + 01) ( + 00 + 000 + 0011 00)(1 + 10) 2
8. Determine whether or not the following claim is true for all regular expressions r1 and
r2 . The symbol stands for equivalence regular expressions in the sense that both
expressions denote the same language. r1 (r1 + r2 ) (r1 + r2 ) .
Answer.
Since L(r1 (r1 + r2 ) ) L((r1 + r2 ) (r1 + r2 ) ) = L((r1 + r2 ) ) and L((r1 + r2 ) ) =
L((r1 + r2 ) ) L(r1 (r1 + r2 ) ), they are equivalent. 2
9. Find an nfa that accepts the language L(aa (a + b)).

Answer.
The following graph represents the NFA M = ({q1, q2, q3}, {a, b}, , q1, {q3}) that
accepts L(aa (a + b)), where is described as in the graph. 2
2
10. Use the construction in Theorem 3.1 to find an nfa that accepts the language L(ab aa+
bba ab).
Answer.
By Theorem 3.1, the automata for L(a) is
By Theorem 3.1, the automata for L(a ) is
The automata for L(b) and L(b ) can be constructed in a similar way.
Then by Theorem 3.1, the automata for L(ab aa) is
Then by Theorem 3.1, the automata for L(bba ab) is
Thus, by Theorem 3.1, the automata for L(ab aa + bba ab) is 2
3
11. Find dfa that accept L = L(ab a ) L((ab) ba).
Answer. L = L(ab a ) L((ab) ba) = {abba}. The following graph represents the
DFA M = ({q0 , q1 , . . . , q5 }, {a, b}, , q0 , {q4 }) that accepts L, where is described as
in the graph. 2
12. Find regular expression for the language accepted by the following automata.
Answer.
We first convert the given nfa to a complete GTG as follows.
Then we reduce the state q1 to obtain a two states one as follows.
4
Then we have:
Finally, we obtain a regular expression: a (ab + c + a(a + b) (a + b))(a + b ) 2
13. Find a regular expression for L = {w : (na (w) nb (w)) mod 3 = 1} on {a, b}.
Answer.
The following figure shows the dfa of the language L, where
q0 : the state for na (w) nb (w) mod 3 = 0;

Then, we use reduce the steps to obtain the following nfa:
Finally the regular expression is ((ba) (a + bb))((ab) + (b + aa)(ba) (a + bb)) . 2
5
14. Construct a dfa that accepts the language generated by the grammar
S abA,
A baB,
B aA|bb.
Answer.
The dfa is constructed as follows, where qx corresponds to variable x, x {S, A, B}.
2
15. Find a regular grammar for L = {w : |(na (w) nb (w))| is odd} on {a, b}.
Answer.
S aA|bA
A aS|bS|
2

HW2 Solutions 2016 Spring

Uploaded by

Copyright:

Available Formats

HW2 Solutions 2016 Spring

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

HW2 Solutions 2016 Spring

Uploaded by

Copyright:

Available Formats

Introduction to Formal Language, Fall 2016 Due: 22-Mar-2016

2. Find a regular expression for the set {an bm : (n + m) is even}.

n and m are even: (aa) (bb );

3. Give a regular expression for L = {an bm : n < 4, m 3}.

4. What languages do the expressions ( ) and a denote?

5. Find a regular expression for L = {vwv : v, w {a, b} , |v| 3}.

9. Find an nfa that accepts the language L(aa (a + b)).

By Theorem 3.1, the automata for L(a ) is

Then by Theorem 3.1, the automata for L(bba ab) is

Thus, by Theorem 3.1, the automata for L(ab aa + bba ab) is 2

Then we reduce the state q1 to obtain a two states one as follows.

Finally, we obtain a regular expression: a (ab + c + a(a + b) (a + b))(a + b ) 2

q0 : the state for na (w) nb (w) mod 3 = 0;

Then, we use reduce the steps to obtain the following nfa:

Finally the regular expression is ((ba) (a + bb))((ab) + (b + aa)(ba) (a + bb)) . 2

You might also like