Homework 2 Problems

CS 162

October 8, 2015

Homework 2 Problems

1. Exercise 2.5.2 on page 79 of Hopcroft et al.

Consider the following -NFA.

ab

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}

Fall 2015 Timothy Johnson

(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:

a

b

c

! {p, q, r} {q, r} {r} ;

{p, q, r} {p, q, r}

; ;

{q, r} {r} ; ;

{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 + )(001)0 This is the language of strings with no two consecutive 1's. (b) (01)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:

01

! q1 q2 q3

q2 q1 q3 q1 q3 q2

(a) Give all the regular expressions Ri(j0). Note: Think of state qi as if it were the state with integer number i.

2

R1(01) = 1 + R1(02) = 0 R1(03) = ; R2(01) = 1 R2(02) = R2(03) = 0 R3(01) = ; R3(02) = 1 R3(03) = 0 + (b) Give all the regular expressions Ri(j1). Try to simplify the expressions as much as possible.

3

R1(11) = R1(01) + R1(01)(R1(01))R1(01) = (1 + ) + (1 + )(1 + )(1 + ) = 1

R1(12) = R1(02) + R1(01)(R1(01))R1(02) = 0 + (1 + )(1 + )0 = 10

R1(13) = R1(03) + R1(01)(R1(01))R1(03) =;

R2(11) = R2(01) + R2(01)(R1(01))R1(01) = 1 + 1(1 + )(1 + ) = 1+

R2(12) = R2(02) + R2(01)(R1(01))R1(02) = + 1(1)0 = + 1+0

R2(13) = R2(03) + R2(01)(R1(01))R1(03) =0

R3(11) = R3(01) + R3(01)(R1(01))R1(01) =;

R3(12) = R3(02) + R3(01)(R1(01))R1(02) =1

R3(13) = R3(03) + R3(01)(R1(01))R1(03) =0+

(c) Give all the regular expressions Ri(j2). Try to simplify as much as possible.

4

R1(21) = R1(11) + R1(12)(R2(12))R2(11) = 1 + 1 0( + 1+0)1+ = (1 + 01)

R1(22) = R1(12) + R1(12)(R2(12))R2(12) = R1(12)(R2(12)) = 10( + 1+0) = (1 + 01)0

R1(23) = R1(13) + R1(12)(R2(12))R2(13) = ; + 10( + 1+0)0 = (1 + 01)00

R2(21) = R2(11) + R2(12)(R2(12))R2(11) = (R2(12))R2(11) = ( + 1+0)1+ = 1+( + 01+)

R2(22) = R2(12) + R2(12)(R2(12))R2(12) = (R2(12))+ = ( + 1+0)+ = (1+0)

R2(23) = R2(13) + R2(12)(R2(12))R2(13) = (R2(22))R2(13) = ( + 1+0)0 = (1+0)0

R3(21) = R3(11) + R3(12)(R2(12))R2(11) = ; + 1( + 1+0)1+ = 1(1+0)1+

R3(22) = R3(12) + R3(12)(R2(12))R2(12) = 1 + 1( + 1+0)+ = 1(1+0)

R3(23) = R3(13) + R3(12)(R2(12))R2(13) = (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.

Google Online Preview   Download