Formal Language and Automata Homework 3 Answer

       

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

\[c^*a(a+c)^*b(a+b+c)^*+c^*b(b+c)^*a(a+b+c)^*\]

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

\[(0+1)^*1(0+1)(0+1)(0+1)(0+1)(0+1)(0+1)(0+1)(0+1)(0+1)\]

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

\[(0+10)^*(11 + 1 + \epsilon)(0+01)^*\]

   

  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.

\[(\epsilon+(10+0)^*11)(01+1)^*(\epsilon+0)\]

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

\[1^*(01^*01^*01^*01^*01^*)^*\]

   

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

(a) $(1+ϵ)(00^∗1)^∗0^∗$.

  • 두 개의 $1$이 연속적으로 나타나지 않는 모든 문자열

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

  • 세 개의 $0$이 연속적으로 최소 $1$번 존재하는 모든 문자열

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

  • 두 개 이상의 $1$이 연속적으로 나타나는 경우, 반드시 문자열의 끝 부분에 존재하는 모든 문자열

   

  1. Here is a transition table for a DFA.

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

​ $R_{11}^{(0)} = 1+\epsilon$, $R_{12}^{(0)} =0$, $R_{13}^{(0)}=\emptyset$

​ $R_{21}^{(0)} = 1$, $R_{22}^{(0)}=\epsilon$, $R_{23}^{(0)}=0$,

​ $R_{31}^{(0)} = \emptyset$, $R_{32}^{(0)} = 1$, $R_{33}^{(0)} = 0+\epsilon$

(b) Give all the regular expressions $R_{ij}^{(1)}$.

​ $R_{11}^{(1)} = 1^* , R_{12}^{(1)} =1^* 0, R_{13}^{(1)}=\emptyset$

​ $R_{21}^{(1)} = 1^+$, $R_{22}^{(1)}=\epsilon+1^+0$, $R_{23}^{(1)}=0$,

​ $R_{31}^{(1)} = \emptyset$, $R_{32}^{(1)} = 1$, $R_{33}^{(1)} = 0+\epsilon$

(c) Give all the regular expressions $R_{ij}^{(2)}$.

​ $R_{11}^{(2)} = 1^* + 1^* 0(\epsilon+1^+0)^* 1^+ = (1+01)^*$,

​ $R_{12}^{(2)} =1^* 0(\epsilon+1^+0)^*$,

​ $R_{13}^{(2)}=\emptyset + 1^* 0(\epsilon+1^+ 0)^* 0$,

​ $R_{21}^{(2)} = (\epsilon+1^+0)^* 1^+ =1^+ (\epsilon+01^+)$,

​ $R_{22}^{(2)}=(\epsilon+1^+0)^+=(1^+0)^*$,

​ $R_{23}^{(2)}=(\epsilon+1^+ 0)^* 0=(1^+ 0)^* 0$,

​ $R_{31}^{(2)} = \emptyset + 1(\epsilon+1^+ 0)^* 1^+ = 1(1^+0)^* 1^+$,

​ $R_{32}^{(2)} = 1+1(\epsilon+1^+0)^+=1(1^+0)^*$,

​ $R_{33}^{(2)} = (0+\epsilon)+1(\epsilon+1^+0)^* 0=0+1(1^+0)^* 0+\epsilon$

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

​ $R_{13}^{(3)} =R_{13}^{(2)}(R_{33}^{(2)})^* = (\emptyset + 1^* 0(\epsilon+1^+0)^* 0)(0+1(1^+0)^* 0+\epsilon)^*$,

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

4e

Regular expression: $(1+01)^* 00(0+10)^* (11(1+01)^* 00(0+01)^* )^*$    

  1. Convert the following DFA to a regular expression, using the state-elimination technique.
\[(1^* +(00+010^* 1)(10+110^* 1)^* 0)^*\]

   

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

(a) $01^*$: 6a

(b) $(0+1)01$ : 6b

(c) $00(0+1)^*$ : 6c

   

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