- Submission Guideline: Upload your homework file (
hw3_[your student id].doc
orhw3_[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.
- 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$
- 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$
- 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^*$.
- 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$.
- 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$ |
- 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. \[ (0+1)^* 1(0+1)+(0+1)^* 1(0+1)(0+1). \]