Formal Language and Automata Homework 2 Answer

       

  1. In Fig 2.8 is a marble-rolling toy. A marble is dropped at $A$ or $B$. Levers $x_1, x_2$ and $x_3$ cause the marble to fall either to the left or to the right. Whenever a marble encounters a lever, it causes the lever to reverse before the marble passes, so the next marble will take the opposite branch.

a) Model this toy by a finite automaton. Let the inputs $A$ and $B$ represent the input into which the marble is dropped. Let acceptance correspond to the marble exiting $D$; nonacceptance represents a marble exiting at $C$. (0 : left, 1 : right, a : acceptance, r : rejection)

  state $A$ $B$
$\rightarrow$ 000r 110a 001a
  110a 010r 111a
  010r 100r 001a
  100r 000r 101a
  001a 111a 010a
  111a 001r 110r
  011r 101r 000r
  101r 001r 110a
  001r 111a 010a
  011a 101r 000r
  101a 001r 110a
  010a 100r 011a

   

  1. Let $A$ be a DFA and $q$ a particular state of $A$, such that $\delta(q,a) = q$ for all input symbols $a$. Show by induction on the length of the input that for all input strings $w$, $\hat{\delta}{(q,w)}=q$.

i) $\lvert w \rvert = 0 $, $w = \epsilon$, $\delta(q,\epsilon) = q$

ii) $\lvert w \rvert = l $, $\delta(q,w) = q$라고 가정하자.

iii) $\lvert wa \rvert = l+1 $, $\hat{\delta}(q,wa) =\hat{\delta}(\delta(q,w),a)=\hat{\delta}(q,a) = q $

따라서, 모든 input $w$에 대하여 $\hat{\delta}{(q,w)}=q$가 성립한다.

   

  1. Let $A$ be a DFA and $a$ a particular input symbol of $A$, such that for all states $q$ of $A$ we have $\delta{(q,a)} = q$. Show by induction on $n$ that for all $n \geq 0, \hat{\delta}(q,a^n) = q $, where $a^n$ is the string consisting of $n$ $a’s$.

우선, $\hat{\delta}(q,a) = q $가 성립한다고 가정하자.

i) $n=0$, $a^0 = \epsilon$, $\hat{\delta}(q,\epsilon) = q $

ii) $n=k$, $\hat{\delta}(q,a^k) = q$와 $\delta(q,a^k) = q$가 성립한다고 가정하자.

iii) $n = k+1$, $\hat{\delta}(q,a^{k+1}) =\hat{\delta}(q,a^k\times a)=\hat{\delta}(\delta(q,a^k),a) = \hat{\delta}(q,a) = q $

   

  1. Convert the following NFA to a DFA and informally describe the language it accepts.
  state $0$ $1$
$\rightarrow$ ${\{p}\}$ ${\{p,q}\}$ ${\{p}\}$
  ${\{p,q}\}$ ${\{p,q,r,s}\}$ ${\{p,t}\}$
$*$ ${\{p,q,r,s}\}$ ${\{p,q,r,s}\}$ ${\{p,t}\}$
$*$ ${\{p,t}\}$ ${\{p,q}\}$ ${\{p}\}$

   

5.

  • 5-(a) a

  • 5-(b) a

  • 5-(c) c    

6. a, b, and c

   

  1. Convert each if your NFA’s from Exercise 6-(a),(b),(c) to DFA’s.

(a)

  state $a$ $b$ $c$ $d$
$\rightarrow$ ${\{q_0}\}$ ${\{q_0,q_1,q_4,q_7}\}$ ${\{q_0}\}$ ${\{q_0}\}$ ${\{q_0}\}$
  ${\{q_0,q_1,q_4,q_7}\}$ ${\{q_0,q_1,q_4,q_7,q_8}\}$ ${\{q_0,q_2,q_5}\}$ ${\{q_0}\}$ ${\{q_0}\}$
  ${\{q_0,q_1,q_4,q_7,q_8}\}$ ${\{q_0,q_1,q_4,q_7,q_8}\}$ ${\{q_0,q_2,q_5}\}$ ${\{q_0,q_9}\}$ ${\{q_0}\}$
  ${\{q_0,q_2,q_5}\}$ ${\{q_0,q_1,q_4,q_7}\}$ ${\{q_0}\}$ ${\{q_0,q_3}\}$ ${\{q_0,q_6}\}$
  ${\{q_0,q_9}\}$ ${\{q_0,q_1,q_4,q_7}\}$ ${\{q_0}\}$ ${\{q_0}\}$ ${\{q_0,q_{10}}\}$
$*$ ${\{q_0,q_3}\}$ ${\{q_0,q_1,q_4,q_7}\}$ ${\{q_0}\}$ ${\{q_0}\}$ ${\{q_0}\}$
$*$ ${\{q_0,q_6}\}$ ${\{q_0,q_1,q_4,q_7}\}$ ${\{q_0}\}$ ${\{q_0}\}$ ${\{q_0}\}$
$*$ ${\{q_0,q_{10}}\}$ ${\{q_0,q_1,q_4,q_7}\}$ ${\{q_0}\}$ ${\{q_0}\}$ ${\{q_0}\}$

(b)

  state $0$ $1$
$\rightarrow$ ${\{q_0}\}$ ${\{q_0,q_1,q_8}\}$ ${\{q_0,q_5}\}$
  ${\{q_0,q_1,q_8}\}$ ${\{q_0,q_1,q_8}\}$ ${\{q_0,q_2,q_5,q_9}\}$
  ${\{q_0,q_5}\}$ ${\{q_0,q_1,q_6,q_8}\}$ ${\{q_0,q_5}\}$
  ${\{q_0,q_2,q_5,q_9}\}$ ${\{q_0,q_1,q_3,q_6,q_8}\}$ ${\{q_0,q_5,q_{10}}\}$
  ${\{q_0,q_1,q_6,q_8}\}$ ${\{q_0,q_1,q_8}\}$ ${\{q_0,q_2,q_5,q_7,q_9}\}$
  ${\{q_0,q_1,q_3,q_6,q_8}\}$ ${\{q_0,q_1,q_8}\}$ ${\{q_0,q_2,q_4,q_5,q_7,q_9}\}$
$*$ ${\{q_0,q_5,q_{10}}\}$ ${\{q_0,q_1,q_6,q_8}\}$ ${\{q_0,q_5}\}$
$*$ ${\{q_0,q_2,q_5,q_7,q_9}\}$ ${\{q_0,q_1,q_3,q_6,q_8}\}$ ${\{q_0,q_5,q_{10}}\}$
$*$ ${\{q_0,q_2,q_4,q_5,q_7,q_9}\}$ ${\{q_0,q_1,q_3,q_6,q_8}\}$ ${\{q_0,q_5,q_{10}}\}$

(c)

  state $a$ $b$ $c$
$\rightarrow$ ${\{q_0}\}$ ${\{q_0,q_1}\}$ ${\{q_0,q_3}\}$ ${\{q_0,q_5}\}$
  ${\{q_0,q_1}\}$ ${\{q_0,q_1}\}$ ${\{q_0,q_2,q_3}\}$ ${\{q_0,q_5}\}$
  ${\{q_0,q_3}\}$ ${\{q_0,q_1}\}$ ${\{q_0,q_3}\}$ ${\{q_0,q_4,q_5}\}$
  ${\{q_0,q_5}\}$ ${\{q_0,q_1,q_6}\}$ ${\{q_0,q_3}\}$ ${\{q_0,q_5}\}$
$*$ ${\{q_0,q_2,q_3}\}$ ${\{q_0,q_1}\}$ ${\{q_0,q_3}\}$ ${\{q_0,q_4,q_5}\}$
$*$ ${\{q_0,q_4,q_5}\}$ ${\{q_0,q_1,q_6}\}$ ${\{q_0,q_3}\}$ ${\{q_0,q_5}\}$
$*$ ${\{q_0,q_1,q_6}\}$ ${\{q_0,q_1}\}$ ${\{q_0,q_2,q_3}\}$ ${\{q_0,q_5}\}$

   

  1. (a)

$CL(p) = \{p\}$

$CL(q) = \{p,q\}$

$CL(r) = \{p,q,r\}$

(b)

  state $a$ $b$ $c$
$\rightarrow$ ${\{p}\}$ ${\{p}\}$ ${\{p,q}\}$ ${\{p,q,r}\}$
  ${\{p,q}\}$ ${\{p,q}\}$ ${\{p,q,r}\}$ ${\{p,q,r}\}$
* ${\{p,q,r}\}$ ${\{p,q,r}\}$ ${\{p,q,r}\}$ ${\{p,q,r}\}$

   

  1. (a)

$CL(p) = \{p,g,r\}$

$CL(q) = \{q\}$

$CL(r) = \{r\}$

(b)

  state $a$ $b$ $c$
$\rightarrow$* ${\{p}\}$ ${\{p,q,r}\}$ ${\{q,r}\}$ ${\{p,q,r}\}$
* ${\{q,r}\}$ ${\{p,q,r}\}$ ${\{r}\}$ ${\{p,q,r}\}$
* ${\{p,q,r}\}$ ${\{p,q,r}\}$ ${\{q,r}\}$ ${\{p,q,r}\}$
* ${\{r}\}$ $\emptyset$ $\emptyset$ $\emptyset$