Math Problems Vault

Example 2.23

An NFA $M=\left(Q,\left\{ 0,1\right\} , \delta , q_{0}, F\right)$ is given by $Q=\left\{ q_{0}, q_{1}, q_{2}\text{, }q_{3}, q_{4}, q_{5}\right\} , F=\left\{ q_{3}, q_{4}\right\}$ , and

$\delta$	0	1	$\varepsilon$
$q_{0}$	$\left\{ q_{0}\right\}$	$\left\{ q_{0}, q_{2}\right\}$	$\left\{ q_{1}\right\}$
$q_{1}$	$\left\{ q_{5}\right\}$	$\left\{ q_{2}\right\}$	-
$q_{2}$	$\left\{ q_{3}\right\}$	-	-
$q_{3}$	-	-	$\left\{ q_{4}\right\}$
$q_{4}$	$\left\{ q_{3}\right\}$	-	-
$q_{5}$	-	$\left\{ q_{4}\right\}$	-

(See Figure 2.29(a) for the transition diagram of $M$ .) Find a DFA which is equivalent to the NFA $M$ .

Figure 2.29: Converting an NFA to a DFA.

?

Example 2.24

Construct a DFA which is equivalent to the NFA $M=(\left\{ p, q\text{, }r\right\} ,\left\{ 0,1\right\} , \delta , p,\left\{ q, r\right\} )$ , where

$\delta$	0	1
$p$	$\left\{ p, q\right\}$	$\left\{ p\right\}$
$q$	-	$\left\{ r\right\}$
$r$	-	-

?

Example 2.26

Let $M=(\left\{ p, q, r, s\right\} ,\left\{ 0,1\right\} , \delta , p,\left\{ q, s\right\} )$ be an $N F A$ given by

$\delta$	0	1
$p$	$\left\{ q, s\right\}$	$\left\{ q\right\}$
$q$	$\left\{ r\right\}$	$\left\{ q, r\right\}$
$r$	$\left\{ s\right\}$	$\left\{ p\right\}$
$s$	-	$\left\{ p\right\}$

Construct an NFA that accepts $\overline{L(M)}$ .

?

Example 2.27

Construct a DFA accepting the set of all binary strings in which the fifth symbol from right is 0.

?

Example 2.28

Consider the following multiplication table on $\left\{ a, b, c\right\}$ :

$\times$	$a$	$b$	$c$
$a$	$c$	$a$	$b$
$b$	$b$	$c$	$a$
$c$	$c$	$b$	$c$

For any string $w$ in $\left\{ a, b, c\right\}^{+}$ , denote by $\operatorname {value}(w)$ the value obtained by multiplying symbols in $w$ from left to right. For instance, let $w=a b c b$ . Then, we get

\begin{aligned} \operatorname {value}(w) & =((a \times b) \times c) \times b=(a \times c) \times b=b \times b=c, \text{ and } \\ \operatorname {value}\left(w^{R}\right) & =((b \times c) \times b) \times a=(a \times b) \times a=a \times a=c. \end{aligned}

Construct an NFA for the set $L$ of all strings $w$ over $\left\{ a, b, c\right\}$ such that $\operatorname {value}(w)=\operatorname {value}\left(w^{R}\right)$ . (E.g., $a b c b \in L$ and $a b b \notin L$ .)

?

Problem 2.4.1

(a)(b)(c)(d)

Convert each of the following NFA's into an equivalent DFA:

?

(a)

The NFA $M=(\left\{ p, q, r\right\} ,,\left\{ 0,1\right\} , \delta , p,\left\{ q, r\right\} )$ , with

$\delta$	0	1
$p$	$\left\{ p\right\}$	$\left\{ p, q\right\}$
$q$	$\left\{ r\right\}$	-
$r$	-	-

(b)

The NFA $M$ of Figure 2.27(a).

(c)

The NFA $M$ of Figure 2.27(b).

(d)

The NFA $M$ of Figure 2.27(c).

Problem 2.4.2

(a)(b)(c)(d)

For each of the following languages, construct a DFA that accepts the language:

?

(a)

The set of binary strings that contain both substring 010 and substring 101.

(b)

The set of all binary strings ending with 00 or 01 or 10.

(c)

The set of binary strings that contain both 001 and 110 as substrings or contain neither 001 nor 110 as a substring.

(d)

The set of binary strings in which both the fourth symbol from the right and the fourth from the left symbols are 0. [Note: Both strings 0110 and 10101 belong to this set.]

Problem 2.4.3

(a)(b)(c)

Consider the following multiplication table on $\left\{ a, b, c\right\}$ :

$\times$	$a$	$b$	$c$
$a$	$a$	$c$	$b$
$b$	$a$	$b$	$c$
$c$	$c$	$c$	$a$

Construct NFA's for the following languages:

?

(a)

$\left\{ x \mid \operatorname {value}(x) \neq \operatorname {value}\left(x^{R}\right)\right\}$ .

(b)

$\left\{ x y \mid \operatorname {value}(x)=\operatorname {value}\left(y^{R}\right)\right\}$ .

(c)

$\left\{ x y \mid \operatorname {value}(x)=\operatorname {value}(y)\right\}$ .