- 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 | 011a | |
| 100r | 000r | 101a | |
| $*$ | 001a | 111a | 010a |
| $*$ | 111a | 011r | 100r |
| 011r | 101r | 000r | |
| 101r | 001r | 110a | |
| 001r | 111a | 010a | |
| $*$ | 011a | 101r | 000r |
| $*$ | 101a | 001r | 110a |
| $*$ | 010a | 100r | 011a |
- 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$가 성립한다.
- 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 $
- 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)
-
5-(b)
-
5-(c)
6.
-
6-(b)
-
6-(c)
- 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}\}$ |
- (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}\}$ |
- (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$ |