Math Problems Vault

Example 2.1

Consider a DFA $M=\left(Q, \Sigma , \delta , q_{0}, F\right)$ where $Q=\left\{ q_{0}, q_{1}, q_{2}\text{, }q_{3}\right\} , \Sigma =\left\{ 0,1\right\} , F=\left\{ q_{1}, q_{2}\right\}$ , and $\delta$ is the function defined by the following table:

$\delta$	0	1
$q_{0}$	$q_{1}$	$q_{3}$
$q_{1}$	$q_{2}$	$q_{3}$
$q_{2}$	$q_{2}$	$q_{2}$
$q_{3}$	$q_{3}$	$q_{3}$

Draw the transition diagram of $M$ .

?

Example 2.2

Consider the DFA $M$ given by Figure 2.2 Determine whether $M$ accepts strings 000 and 010.

?

Example 2.3

What is the language $L(M)$ accepted by the $D F A M$ of Figure 2.2?

?

Example 2.4

What is the language $L(M)$ accepted by the DFA $M$ of Figure 2.3?

?

Example 2.5

What is the language $L(M)$ accepted by the $D F A M$ of Figure 2.4?

?

Problem 2.1.1

(a)(b)(c)

Consider the DFA $M$ with the transition diagram of Figure 2.5.

?

(a)

Which state is the initial state of $M$ , and which states are the final states of $M$ ?

(b)

For each of the strings 0001, 010101, and 001110101101, find the computation path of $M$ on the string and determine whether $M$ accepts it.

(c)

Among all strings in (01)*, which ones are in $L(M)$ ?

Figure 2.5: DFA of Exercise 1.

Problem 2.1.2

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

For integers $n, d \geq 1$ , consider a DFA $M_{n, d}=\left(Q, \Sigma , \delta , q_{0}, F\right)$ , where $Q= \left\{ q_{0}, q_{1}, q_{2}, \cdots , q_{n-1}\right\} , \Sigma =\left\{ a_{0}, a_{1}, \cdots , a_{d-1}\right\} , \delta \left(q_{i}, a_{k}\right)=q_{(d i+k) \bmod n}$ , and $F=\left\{ q_{1}\right\}$ .

?

(a)

Draw the transition diagram of $M_{n, d}$ with $n=7$ and $d=2$ .

(b)

Suppose $n=7, d=2, a_{0}=0$ and $a_{1}=1$ . Find $\delta \left(q_{3}, 0101\right)$ and $\delta \left(q_{1}, 11010\right)$ .

(c)

Suppose $n=7, d=2, a_{0}=0$ and $a_{1}=1$ . Find binary strings $x$ and $y$ such that $\delta \left(q_{0}, x\right)=q_{5}$ and $\delta \left(q_{0}, y\right)=q_{6}$ .

(d)

Show that for any state $q_{j} \in Q$ , there exists a string $x \in \Sigma^{*}$ such that $\delta \left(q_{0}, x\right)=q_{j}$ .

Figure 2.6: Three DFA’s of Exercise 3.

Problem 2.1.3

For each of the DFA's $M_{1}, M_{2}$ and $M_{3}$ , as shown in Figure 2.6(a), (b) and (c), respectively, describe in English the language accepted by it.

?