- 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 + \epsilon)(0+01)^*\]
- 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^*)^*\]
- 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$이 연속적으로 나타나는 경우, 반드시 문자열의 끝 부분에 존재하는 모든 문자열
- 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$.
Regular expression: $(1+01)^* 00(0+10)^* (11(1+01)^* 00(0+01)^* )^*$
- Convert the following DFA to a regular expression, using the state-elimination technique.
- Convert the following regular expressions to NFA’s with $\epsilon$-transitions.
(a) $01^*$:
(b) $(0+1)01$ :
(c) $00(0+1)^*$ :
- Use the distributive laws to develop two different, simpler, equivalent expressions.