Start

Figure 3.18: Automata constructed for Example 3.8

Fig. 3.18(c). Note that this c-NFA, when e-transitions are removed, looks just like the much simpler automaton of Fig. 3.15 that also accepts the strings that have a 1 in their next-to-last position. □

3.2.4 Exercises for Section 3.2

Exercise 3.2.1: Here is a transition table for a DFA:

* a) Give all the regidar expressions RK Note: Think of state qi as if it were

the state with integer number i.

* b) Give all the regular expressiOn.s R] TVy to simplify the expressions as

much as possible.

c) Give all the regular expressions RJ . Try to simplify the expressions as imicji as possible.

d) Giv{; a regular expression for the language of the automaton.

* e) Construct the transition diagram for the DFA and give a regular expres-

sion for its language by eliminating state 92-

Exercise 3.2.2: Repeat Exercise 3.2.1 for the following DFA:

Note that solutions to parts (a), (b) and (e) are not available for this exercise.

Exercise 3.2.3: Convert the following DFA to a regular expression, using the state-elimination technique of Section 3.2.2.

Exercise 3.2.4: Convert the following regular expressions to NFAs with e-transitions.

* a) 01*.

b) (0 + 1)01.

c) 00(0 + 1)*.

Exercise 3.2.5: Eliminate e-transitions from your e-NFAs of Exercise 3.2.4. A solution to part (a) appears in the books Web pages.

! Exercise 3.2.6: Let A = (Q, E,,</ot {Q;}) be an e-NFA such that there are no transitions into qo and no transitions out of q/. Describe the language accepted by each of the following modifications of A, in terms of L = L{A):

* a) The automaton constructed from A by adding an e-transition from q/ to

* b) The automaton constructed from A by adding an e-transition from 170

to every state reachable from qo (along a path whose labels may include symbols of S as well as e).

c) The automaton constructed from .4 by adding an e-transition to 9/ from every state that can reach q/ along some path.

d) The automaton constructed from A by doing both (h) and (c).

!! Exercise 3.2.7: There are some simplifications to the constructions of Theorem 3.7, where we converted a regular expression to an e-NFA. Here are three:

1. For the union operator, instead of creating new start and accepting states, merge the two start states into one state with all the transitions of both start states. Likewise, merge the two accepting states, having all transitions to either go to the merged state insteatl.

2. For the concatenation operator, merge the accepting state of the first automaton with the start state of the second.

3. For the closure operator, shnply add e-transitions from the accepting state to the start state and vice-versa.

Each of these simplifications, by themselves, still yield a correct construction; that is, the resulting e-NFA for any regular expression accepts the language of the expression. Which subsets of changes (1), (2), and (3) may be made to the construction together, while still yielding a correct automaton for every regular expression?

*!! Exercise 3.2.8: Give an algorithm that tafes a DFA A and computes the number of strings of length n (for some given n, not related to the number of states of A) accepted by A. Your algorithm should be polynomial in both n and the number of states of A. Hint: Use the technique suggested by the construction of Theorem 34.