Homework 2 Problems
CS 162
Fall 2015
Homework 2 Problems
October 8, 2015
Timothy Johnson
1. Exercise 2.5.2 on page 79 of Hopcroft et al.
Consider the following ?-NFA.
?
a
b
c
! p {q, r}
;
{q}
{r}
q
;
{p} {r} {p, q}
?r
;
;
;
;
(a) Compute the ?-closure of each state.
p ! {p, q, r}
q ! {q}
r ! {r}
(b) Give all the strings of length three or less accepted by the automaton.
?, a, b, c, ba, bb, bc, ca, cb, cc, aaa, aab, aac, aba, abb, baa, bab, bac, bca, bcb, bcc,
caa, cab, cac, cba, cbb, cbc, cca, ccb, ccc
(c) Convert the automaton to a DFA. (Please construct the table, and then draw the diagram.)
We first construct the table below:
! ?{p, q, r}
?{q, r}
?{r}
;
a
{p, q, r}
{p, q, r}
;
;
b
{q, r}
{r}
;
;
c
{p, q, r}
{p, q, r}
;
;
1
2. Exercise 3.1.1 on page 91 of Hopcroft et al.
Write regular expressions for the following languages.
(a) The set of strings over alphabet {a, b, c} containing at least one a and at least one b.
(A + B + C)? (A(A + B + C)? B + B(A + B + C)? A)(A + B + C)?
(b) The set of strings of 0¡¯s and 1¡¯s whose tenth symbol from the right end is 1.
(0 + 1)? 1(0 + 1)9
(c) The set of strings of 0¡¯s and 1¡¯s with at most one pair of consecutive 1¡¯s.
(0 + 10)? (11 + ?)(0 + 10)?
3. Exercise 3.1.4 on page 92 of Hopcroft et al.
Give English descriptions of the languages of the following regular expressions.
(a) (1 + ?)(00? 1)? 0?
This is the language of strings with no two consecutive 1¡¯s.
(b) (0? 1? )? 000(0 + 1)?
This is the language of strings with three consecutive 0¡¯s.
(c) (0 + 10)? 1?
This is the language of strings in which there are no two consecutive 1¡¯s, except for
possibly a string of 1¡¯s at the end.
4. Exercise 3.2.1 on page 107 of Hopcroft et al.
Here is a transition table for a DFA:
! q1
q2
?q3
0
q2
q3
q3
1
q1
q1
q2
(0)
(a) Give all the regular expressions Rij . Note: Think of state qi as if it were the state with
integer number i.
2
(0)
R11 = 1 + ?
(0)
R12 = 0
(0)
R13 = ;
(0)
R21 = 1
(0)
R22 = ?
(0)
R23 = 0
(0)
R31 = ;
(0)
R32 = 1
(0)
R33 = 0 + ?
(1)
(b) Give all the regular expressions Rij . Try to simplify the expressions as much as possible.
3
(1)
(0)
(0)
(0)
(0)
R11 = R11 + R11 (R11 )? R11
= (1 + ?) + (1 + ?)(1 + ?)? (1 + ?)
= 1?
(1)
(0)
(0)
(0)
(0)
R12 = R12 + R11 (R11 )? R12
= 0 + (1 + ?)(1 + ?)? 0
= 1? 0
(1)
(0)
(0)
(0)
(0)
(0)
(0)
(0)
(0)
R13 = R13 + R11 (R11 )? R13
(1)
R21
=;
= R21 + R21 (R11 )? R11
= 1 + 1(1 + ?)? (1 + ?)
= 1+
(1)
(0)
(0)
(0)
(0)
R22 = R22 + R21 (R11 )? R12
= ? + 1(1? )0
= ? + 1+ 0
(1)
(0)
(0)
(0)
(0)
(0)
(0)
(0)
(0)
(0)
(0)
(0)
(0)
(0)
(0)
(0)
(0)
R23 = R23 + R21 (R11 )? R13
=0
(1)
R31 = R31 + R31 (R11 )? R11
(1)
R32
=;
= R32 + R31 (R11 )? R12
=1
(1)
R33
= R33 + R31 (R11 )? R13
=0+?
(2)
(c) Give all the regular expressions Rij . Try to simplify as much as possible.
4
(2)
(1)
(1)
(1)
(1)
R11 = R11 + R12 (R22 )? R21
= 1? + 1 ? 0(? + 1+ 0)? 1+
= (1 + 01)?
(2)
(1)
(1)
(1)
(1)
R12 = R12 + R12 (R22 )? R22
(1)
(1)
= R12 (R22 )?
= 1? 0(? + 1+ 0)?
= (1 + 01)? 0
(2)
(1)
(1)
(1)
(1)
R13 = R13 + R12 (R22 )? R23
= ; + 1? 0(? + 1+ 0)? 0
= (1 + 01)? 00
(2)
(1)
(1)
(1)
(1)
(1)
(1)
(1)
(1)
(1)
(1)
R21 = R21 + R22 (R22 )? R21
(1)
(1)
= (R22 )? R21
= (? + 1+ 0)1+
= 1+ (? + 01+ )
(2)
(1)
(1)
R22 = R22 + R22 (R22 )? R22
(1)
= (R22 )+
= (? + 1+ 0)+
= (1+ 0)?
(2)
(1)
(1)
R23 = R23 + R22 (R22 )? R23
(2)
(1)
= (R22 )? R23
= (? + 1+ 0)? 0
= (1+ 0)? 0
(2)
(1)
(1)
R31 = R31 + R32 (R22 )? R21
= ; + 1(? + 1+ 0)? 1+
= 1(1+ 0)? 1+
(2)
(1)
(1)
(1)
(1)
R32 = R32 + R32 (R22 )? R22
= 1 + 1(? + 1+ 0)+
= 1(1+ 0)?
(2)
(1)
(1)
(1)
(1)
R33 = R33 + R32 (R22 )? R23
= (0 + ?) + 1(? + 1+ 0)? 0
= 0 + 1(1+ 0)? 0 + ?
(d) Give a regular expression for the language of the automaton.
5
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- cs500 homework 1 solutions santa fe institute
- homework 1 problems
- homework 3solutions njit sos
- starting and ending presentations phrases
- homework 2 problems
- question bank solution unit 1 introduction to finite
- solution to problem set 1 university of california san
- homework 2 solutions
- homework 2solutions njit sos
Related searches
- homework for 2 year old
- problems 2018 chevy equinox 2 0t
- 2 digit division problems worksheet
- 2 grade homework for free
- 2 step word problems for 3rd grade
- 2 step word problems printable
- 2 grade homework printable
- 2 step word problems pdf
- homework for 2 year old printable online
- 2 step word problems 2nd grade
- algebra 2 problems and answers
- chapter 8 lesson 2 homework elements and chemical bonds