Section 2.5

Finite Automata and Regular Expressions

[7/43%]
Show
LaTeX
Example 2.29

Find a DFA accepting the language 10+(0+11)0∗110+(0+11) 0^{*} 1.

?
Example 2.30

Construct an NFA accepting the set LL of binary strings of an odd length which contain the substring 00.

?
Example 2.32

Find a regular expression for the language accepted by NFA in Figure 2.29(a).

?
Problem 2.5.1

For each of the following regular expressions rr, construct a DFA that accepts L(r)L(r) :

?
(a)

(0+10)∗(1+01)∗(0+10)^{*}(1+01)^{*}.

(b)

(0+1)∗0(0+1)(0+1)0(0+1)(0+1)^{*} 0(0+1)(0+1) 0(0+1).

(c)

0(0+1)∗0+1(0+1)∗10(0+1)^{*} 0+1(0+1)^{*} 1.

Problem 2.5.2

For each of the following languages, find an NFA that accepts it:

?
(a)

{x#y∣x,y∈(0+1)∗,∣x∣≡∣y∣( mod 2)}\left\{ x \# y \mid x, y \in (0+1)^{*}, \left|x\right| \equiv \left|y\right|(\bmod 2)\right\}.

(b)

{x#y∣x,y∈(0+1)∗,∣x∣+∣y∣≥5}\left\{ x \# y \mid x, y \in (\mathbf{0}+\mathbf{1})^{*}, \left|x\right|+\left|y\right| \geq 5\right\}.

(c)

{x#y∣x,y∈(0+1)∗,∣x∣⋅∣y∣ is dividable by 5}\left\{ x \# y \mid x, y \in (\mathbf{0}+\mathbf{1})^{*}, \left|x\right| \cdot \left|y\right| \text{ is dividable by 5}\right\}.

Problem 2.5.3

Figure 2.41 shows an NFA accepting 0∗0^{*}, constructed based on the method of Example 2.22. The four ε\varepsilon-moves cannot be eliminated by the rule of Theorem 1.25. Apply the method in the proof of Theorem 2.31 to reduce some of its ε\varepsilon-moves. Can you find, from this example, a more general rule (than Theorem 1.25) to eliminate redundant ε\varepsilon-transitions?

Figure 2.41: An NFA accepting 0*.Figure 2.41: An NFA accepting 0*.

?
Problem 2.5.4

For each of the languages accepted by NFA's of Figure 2.42, find a regular expression for it.

Figure 2.42: Two NFA’s for Exercise 4.Figure 2.42: Two NFA’s for Exercise 4.

?