Formal Language and Automata Homework 3

   

  • Submission Guideline: Upload your homework file (hw3_[your student id].doc or hw3_[your student id].hwp) to online Eruri classroom. You are allowed to write down your answers either in Korean or English at your convenience.
  • Deadline : 18:00 PM, Tuesday, September 28

       

Please feel free to leave your questions about homework problems in the online Piazza classroom.

       

  1. Write regular expressions for the following languages.

(a) The set of strings over alphabet $\{a,b,c \} $ containing at least one $a$ and at least one $b$.

  • Example : $ab, abcc, aabc \in L$ and $c,cc, acacca, aaaa, bbccbb \notin L$

(b) The set of strings of $0$’s and $1$’s whose tenth symbol from the right end is $1$.

  • Example : $1000100100, 011010001101 \in L$ and $0, 00, 000, 000000000, 1110011111111 \notin L$

(c) The set of strings of $0$’s and $1$’s with at most one pair of consecutive $1$’s.

  • Example : $011, 110, 101101 \in L$ and $000111, 00110110, 111 \notin L$

   

  1. Write regular expressions for the following languages.

(a) The set of strings of $0$’s and $1$’s such that every pair of adjacent $0$’s appears before any pair of adjacent $1$’s.

  • Example : $0, 1, 1010, 0011, 000111, 00011011 \in L$ and $00, 111110000, 110011 \notin L$

(b) The set of strings of $0$’s and $1$’s whose number of $0$’s is divisible by five.

  • Example : $\epsilon, 1111, 0100100, 10110101000010100\in L$ and $0000, 11001100, 001100, 01010101010 \notin L$

   

  1. Give Korean descriptions of the languages of the following regular expressions.

(a) $(1+\epsilon)(00^* 1)^* 0^*$.

(b) $(0^* 1^* )^* 000(0+1)^*$.

(c) $(0+10)^* 1^*$.

   

  1. Here is a transition table for a DFA.
  State $0$ $1$
$\rightarrow $ $q_1$ $q_2$ $q_1$
  $q_2$ $q_3$ $q_1$
$*$ $q_3$ $q_3$ $q_2$

(a) Give all the regular expressions $R_{ij}^{(0)}$.

Note: Think of state $q_i$ as if were the state with integer number $i$.

(b) Give all the regular expressions $R_{ij}^{(1)}$. Try to simplify the expressions as much as possible.

(c) Give all the regular expressions $R_{ij}^{(2)}$. Try to simplify the expressions as much as possible.

(d) Give a regular expression for the language of automaton.

(e) Construct the transition diagram for the DFA and give a regular expression for its language by eliminating state $q_2$.

   

  1. Convert the following DFA to a regular expression, using the state-elimination technique.
  State $0$ $1$
$\rightarrow *$ $p$ $s$ $p$
  $q$ $p$ $s$
  $r$ $r$ $q$
  $s$ $q$ $r$

   

  1. Convert the following regular expressions to NFA’s with $\epsilon$-transitions.

(a) $01^*$.

(b) $(0+1)01$.

(c) $00(0+1)^*$.

   

  1. Use the distributive laws to develop two different, simpler, equivalent expressions. \[ (0+1)^* 1(0+1)+(0+1)^* 1(0+1)(0+1). \]