Math Problems Vault

Example 2.17

Find an NFA that accepts the set of binary strings having a substring 010.

?

Example 2.18

Find an NFA that accepts the set of binary strings beginning with 010 or ending with 110.

?

Example 2.19

Find an NFA that accepts the set of binary strings with at least two occurrences of substring 01 and ends with 11.

Figure 2.22: The Solution to Example 2.19.

?

Example 2.20

Find an NFA that accepts the set $\left\{ 0^{n} 10^{m} \mid n, m \geq 0, n \equiv m(\bmod 5)\right\}$ .

?

Example 2.21

Let $M_{1}$ and $M_{2}$ be two NFA's. Construct an NFA $M$ such that $L(M)=L\left(M_{1}\right) \cdot L\left(M_{2}\right)$ .

?

Example 2.22

Let $M_{1}$ be an NFA. Construct an NFA $M$ such that $L(M)= L\left(M_{1}\right)^{*}$ .

?

Problem 2.3.1

(a)(b)(c)

Consider the NFA $M$ of Figure 2.26.

?

(a)

What are $\varepsilon$ -closure $\left(\left\{ q_{0}\right\} \right)$ and $\varepsilon$ -closure $\left(\left\{ q_{1}, q_{2}, q_{3}\right\} \right)$ ?

(b)

What are $\delta \left(\left\{ q_{0}\right\} , 0\right)$ and $\delta \left(\left\{ q_{2}, q_{3}\right\} , 1\right)$ ?

(c)

Draw the computation trees of $M$ on strings $x=011$ and $y=101$ . Does $M$ accept or reject $x$ and $y$ ?

Figure 2.26: The NFA of Exercise 1.

Problem 2.3.2

For each NFA $M$ shown in Figure 2.27, determine what $L(M)$ is.

?

Problem 2.3.3

For each of the following languages, construct an NFA that accepts the language:

?

(a)

The set of binary strings that contain at least three occurrences of substring 010.

(b)

The set of binary strings that contain both substrings 010 and 101. [Hint: This is equivalent to the set of binary strings that contain either a substring 0101 or a substring 1010 or a substring 010 followed by 101 or a substring 101 followed by 010.]

(c)

The set of binary strings that contain either a substring 010 or a substring 101, and end with 111 or 000.

(d)

The set of binary strings of which the $(3 n)$ th symbol is 0 for each $n \geq 1$ .

(e)

The set of binary strings $x$ of length $3 n$ for some $n \geq 1$ , such that, for each $1 \leq k \leq n$ , at least one of the $(3 k-2)$ nd, $(3 k-1)$ st and $(3 k)$ th symbols of $x$ is 0.

(f)

The set $\left\{ 0^{n} 10^{m} 10^{q} \mid q \equiv n m(\bmod 5)\right\}$ .

Figure 2.27: Three NFA’s of Exercise 2.

Problem 2.3.4

Prove that the new initial state $s$ and the final state $f$ in the construction of Example 2.22 are necessary. That is, find NFA's $M_{1}$ and $M_{2}$ such that the NFA's $M_{1}^{\prime }$ and $M_{2}^{\prime }$ of Figure 2.28 have the property $L\left(M_{1}^{\prime }\right) \neq L\left(M_{1}\right)^{*}$ and $L\left(M_{2}^{\prime }\right) \neq L\left(M_{2}\right)^{*}$ .

?