Formal Language and Automata Homework 2

   

  • Submission Guideline: Upload your homework file (hw2_[your student id].doc or hw2_[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.

       

  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.

    marble_rolling_toy

    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$

   

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

   

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

   

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

   

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

   

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

    example_6a

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

   

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

   

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

   

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