Problem Set #1
CS 154
due February 17, 2005
Each problem is worth 10 points.
- Find a regular expression for L(M), where M is the DFA whose transition function δ is given below. You should not need to use any of the algorithms of Section 3.2. Use only concatenation and the + and * operators (and parentheses if necessary) for your answer; don't use the Unix-style notation of Section 3.3.
| δ |
0 |
1 |
| q0 |
q2 |
q1 |
| *q1 |
q1 |
q5 |
| q2 |
q3 |
q2 |
| q3 |
q4 |
q2 |
| *q4 |
q5 |
q5 |
| q5 |
q5 |
q5 |
- Give an example of a DFA that accepts exactly those strings over {0,1}
that do not contain 00 or 11 as a substring. Note that all strings of length 0 or 1 should be accepted.
- Prove by induction that if |x| <= |y|, then |xn| <= |yn|. You may use any theorem proved in class.