Regular expressions excercise solutions PDF

Preview

Summary

Regular Expressions Exercise solutions...

Description

Theory of Computation, CSCI 438, Spring 2018 Regular expressions, pg. 63-66, pg. 54-63, Regular expressions describe regular languages, pg. 66-69, Jan. 26 Exercise 1.10 b, 1.15, 1.19 b.

1.10 Use the construction in the proof of Theorem 1.49 to give the state diagrams of NFAs recognizing the star of the languages described in Exercise 1.6 j. Exercise 1.6 Give state diagrams of DFAs recognizing the following languages. In all parts, the alphabet is {0, 1}. j. {w | w contains at least two 0s and at most one 1} A possible DFA is:

Using the construction of Theorem 1.49, to create the Kleene closure of the language, {w | w contains at least two 0s and at most one 1}*.

1

1.15 Give a counter example to show that the construction fails to prove Theorem 1.49, the closure of the class of regular languages under the star operation. Let N1 = (Q1, , 1, q1, F1) recognize A1. Construct N = (Q1, , , q1, F) as follows. N is supposed to recognize A1*. a. The state of N are the states of N1. b. The start state of N is the same as the start state of N1. c. F = {q1}  F1. The accept states F are the old accept states plus its start state. d. Define  so that for any qQ1 and any aε 1(q, a) for q∉F1 or a≠ε  (q,a) = 1(q, a)  {q1} for qF1 and a= ε (Suggestion: Show this construction graphically, as in Figure 1.50.)

Consider L={(00)*1} which is recognized by:

Note that:

Using the construction described for finding a machine for L* gives:

2

However 00L(M’) but 00∉L*. 1.19 Use the procedure described in lemma 1.55 to convert the following regular expression to an NFA. b. (((00)*(11)) 01)* Answer:

3...