Finite Automata

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:

Draw the transition diagram of $M$.

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

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

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

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

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

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\}$.

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.

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

The set of all binary strings beginning with prefix 01.

The set of all binary strings having a substring 00.

The set of all binary strings having the substring 00101.

The set $A$ of all binary strings ending with 01.

The set of all binary expansions of positive integers which are congruent to zero modulo 5.

The set of all binary strings having a substring 00 or ending with 01.

The set of all binary strings having a substring 00 and ending with 01.

The set of all binary strings having a substring 00 but not ending with 01.

The set $L$ of all binary strings in which every block of four consecutive symbols contains a substring 01.

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

For each of the following languages, use the product automaton method to construct a DFA that accepts the language:

For each of the following languages, use the checker method to construct a DFA that accepts the language:

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

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

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.

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

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)$.

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

Consider the NFA $M$ of Figure 2.26.

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

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

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)^{*}$.

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

(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.

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

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

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

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

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

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

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$.)

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

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

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

Construct NFA's for the following languages:

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

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

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

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

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

Figure 2.41 shows an NFA accepting $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*.

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.

Let $M$ be an $N F A$. Construct an $N F A M^{\prime }$ such that $L\left(M^{\prime }\right)= L(M)^{R}$.

Let $f$ be a substitution over $\Sigma$. Assume that $L \subseteq \Sigma^{*}$ is a regular language, and that $f(a)$ is a regular language for each $a \in \Sigma$. Then, $f(L)$ is also a regular language.

Show that for any language $L_{2}$, if $L_{1}$ is regular then $L_{1} / L_{2}$ is also regular.

Let $L$ be a regular language over $\Sigma , k$ a positive integer and $\phi$ a mapping from $\Sigma^{k}$ to $\Sigma$. Prove that

is regular.

Prove that if $L$ is regular, so is $\operatorname {MIN}(L)$.

Show that if $A$ and $B$ are regular languages over $\left\{ 0,1\right\}$, then

is also regular.

Show that if $L$ is a regular language, so is

Show that if $L$ is a regular language, so is

Show that if $L$ is a regular set, so is

Let $A$ and $B$ be two regular languages. Show that the language defined by

is also regular.

Show that if $L$ is regular, so is

Prove the following identity:

For any two bits $a, b \in \left\{ 0,1\right\} , a \oplus b$ denotes the exclusive-or of $a$ and $b$; that is, $0 \oplus 0=1 \oplus 1=0$ and $0 \oplus 1=1 \oplus 0=1$. For any two binary strings $x$ and $y$ with $\left|x\right|=\left|y\right|, x \oplus y$ denotes the bitwise exclusive-or of $x$ and $y$. For example, if $x=0011$ and $y=0101$, then $x \oplus y=0110$. Let $A=001(0+1)^{*}$ and $B=(0+1)^{*} 100$. Find a regular expression for each of the following languages:

Show that if $A$ and $B$ are regular languages, so are the following languages:

Give an alternative proof for Example 2.42 based on the following idea: We may simulate NFA $\bar{M}$ on $x y$ together with $\widehat{M}_{i}$ on $z$ by simulating two moves of $\bar{M}$ and one move of $\widehat{M}_{i}$ at each step. (Thus, the new NFA for $L_{\frac{3}{3}}$ has only $n+2$ tracks.)

Show that if $A$ and $B$ are regular languages, so are the following:

Consider a Boolean function $f\left(a_{1}, a_{2}, \cdots , a_{n}\right)$. For any $n$ binary strings $x_{1}, x_{2}, \cdots , x_{n}$ of equal length, denote by $f\left(x_{1}, x_{2}, \cdots , x_{n}\right)$ the bitwise function $f$ on $x_{1}, x_{2}, \cdots , x_{n}$. That is, if $x_{i}=x_{i_{1}} x_{i_{2}} \ldots x_{i_{k}}$ for $i=1,2$, $\ldots , n$, where each $x_{i_{j}}$ is a bit in $\left\{ 0,1\right\}$, then $f\left(x_{1}, x_{2}, \ldots , x_{n}\right)$ is equal to

Show that if languages $A_{1}, A_{2}, \cdots , A_{n}$ are regular, then language

is also regular.

In Exercise 3(c) above, show that, for any regular language $A$, the number of distinct $A_{x}$ 's is finite. Find an upper bound for this number, assuming that $A$ is accepted by a DFA with $s$ states.

Are the following statements true? Prove or disprove your answer.

Show that every regular language in $0^{*}$ can be represented in the form

for some integer constants $a_{1}, a_{2}, \cdots , a_{k}, b_{1}, b_{2}, \cdots , b_{h}$, and $c$.

A subset $P$ of nonnegative integers is ultimately periodic if there exists two positive integers $b, p$ such that, for all $m \geq b, m \in P$ implies $m+p \in P$. Prove the following statements:

Apply Exercise 10(d) above to prove the following results:

Let $L=\left\{ x \in (0+1)^{*} \mid \left|x\right|\text{ is odd}\right\}$. Find all equivalence classes of $R_{L}$.

Let $L$ be the set of nonempty binary strings starting and ending with the same symbol. Find all equivalence classes of $R_{L}$.

Show that $L$ is regular if and only if there exists a positive integer $k$ such that $x R_{L} y$ if and only if for every $z \in \Sigma^{*}$ with $\left|z\right| \leq k$, $x z \in L \Leftrightarrow y z \in L$.

Find the minimum DFA for language $(0+1)^{*} 01$.

Construct the minimum DFA for language $(0+1)^{*} 0(0+1)^{9}$.

Find the minimum DFA equivalent to the DFA $M$ of Figure 2.47.

Figure 2.47: DFA M.

Show that the following language is not regular:

Show that $L=\left\{ 0^{m} 1^{n} \mid \operatorname {gcd}(m, n)=1\right\}$ is not regular.

For any language $L$, define an equivalence relation $D_{L}$ by

Show that $L$ is regular if and only if $\operatorname {Index}\left(D_{L}\right)<\infty$.

Find all equivalence classess of $R_{L}$ for the following languages:

For each of the following languages $L$, show that $\operatorname {Index}(L)=\infty$ and so $L$ is not regular.

For each of the following languages $L$, show that no two strings can be in the same equivalence class of $R_{L}$.