- Submission Guideline: Upload your homework file (
hw2_[your student id].doc
orhw2_[your student id].hwp
) to online Piazza classroom. You are allowed to write down your answers either in Korean or English at your convenience. - Deadline : 18:00 PM, Friday, September 23
- Note 1: Example state transition table of Problem 1 has been changed to reflect the following description: ‘Whenever a marble encounters a lever, it causes the lever to reverse before the marble passes’.
Please feel free to leave your questions about homework problems in the online Piazza classroom.
-
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$ |
- 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$.
- 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$.
- Convert the following NFA to a DFA and informally describe the language it accepts.
State | $0$ | $1$ | |
---|---|---|---|
$\rightarrow $ | $p$ | ${\{p,q}\}$ | ${\{p}\}$ |
${q}$ | ${\{r,s}\}$ | ${\{t}\}$ | |
${r}$ | ${\{p,r}\}$ | ${\{t}\}$ | |
$*$ | ${s}$ | $\emptyset$ | $\emptyset$ |
$*$ | ${t}$ | $\emptyset$ | $\emptyset$ |
-
Give NFA’s to accept the following languages. Try to take advantage of nondeterministic as much as possible.
a) The set of strings over alphabet ${\{0,1,\ldots,9}\}$ such that the final digit has appeared before.
b) The set of strings over alphabet ${\{0,1,\ldots,9}\}$ such that the final digit has not appeared before.
c) The set of $0$’s and $1$’s such that there are two $0$’s separated by a number of positions that is a multiple of 4. Note that $0$ is an allowable multiple of 4.
-
Design NFA’s to recognize the following sets of strings.
a) The set of strings that end in $abc$, $abd$, and $aacd$. Assume the alphabet is ${\{a,b,c,d}\}$. (a sample solution is provided below.)
b) The set of strings that end in $0101$, $101$, and $011$. Assume the alphabet is $\{0, 1\}$.
c) The set of strings that end in $ab$, $bc$, and $ca$. Assume the alphabet is ${\{a, b, c}\}$.
- Convert each if your NFA’s from Exercise 6-(a),(b),(c) to DFA’s.
- Consider the following $\epsilon$-NFA.
State | $\epsilon$ | $a$ | $b$ | $c$ | |
---|---|---|---|---|---|
$\rightarrow$ | $p$ | $\emptyset$ | ${\{p}\}$ | ${\{q}\}$ | ${\{r}\}$ |
$q$ | ${\{p}\}$ | ${\{q}\}$ | ${\{r}\}$ | $\emptyset$ | |
$*$ | $r$ | ${\{q}\}$ | ${\{r}\}$ | $\emptyset$ | ${\{p}\}$ |
a) Compute the $\epsilon$-closure of each state.
b) Convert the automaton to a DFA.
- Consider the following $\epsilon$-NFA.
State | $\epsilon$ | $a$ | $b$ | $c$ | |
---|---|---|---|---|---|
$\rightarrow$ | $p$ | ${\{q,r}\}$ | $\emptyset$ | ${\{q}\}$ | ${\{r}\}$ |
$q$ | $\emptyset$ | ${\{p}\}$ | ${\{r}\}$ | ${\{p,q}\}$ | |
$*$ | $r$ | $\emptyset$ | $\emptyset$ | $\emptyset$ | $\emptyset$ |
a) Compute the $\epsilon$-closure of each state.
b) Convert the automaton to a DFA.