Comp335 Introduction to Theoretical Computer Science Winter 2023 Assignment 2
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Comp335 Introduction to Theoretical Computer Science
Winter 2023
Assignment 2. Due date: February 16, by 23:59 P.M. EST
No extensions will be granted
1. Give a regular expression for each of the languages below.
(a) {w e {a, b, c}* : na (w) e 1 and nb (w) e 1}.
(b) {w e {0, 1}* : 00 occurs at most twice in w}. Note: 00 occurs twice in 000
2. Use the inductive method of Theorem 3.4 of textbook to find a regular expression for the DFA given by the following transition table:
|
|
a |
b |
|
2 |
q2 q2 |
q1 q1 |
Hint: This question requires a bit of patience as there are twelve Rij(k) expressions to compute. Simplify the expressions as much as possible at each step.
3. Use the state-elimination technique to find a regular expression for the DFA given by the following transition table:
|
|
a |
b |
c |
|
q2 q3 q4 + q5 q6 |
|
q6 q3 q4 q2 q6 q6 |
q2 q6 q5 q6 q6 q6 |
q4 q6 q6 q5 q6 q6 |
4. Convert the following regular expressions to ∈-NFA’s.
(a) (000)* (∈＋011＋001)(111)*
(b) (0＋1)* (001＋010＋100)* (0＋1)*
5. Apply the Pumping Lemma to prove that the following languages are not regular.
(a) {ak bn : n w 2k }
(b) {vw : v e {a, b}* , w e {c, d}* , ∣v∣ w ∣w∣}
6. Complete the proof of Theorem 4.8 of textbook, by showing by an induction on ∣w∣ that δˆ((qL , qM ), w) w (δˆL (qL , w), δˆM (qM , w))
7. Let h be the homomorphism h : {a, b} → {0, 1}* given by h(a) w 01, h(b) w 011, and define L w {w e {0, 1}* : n1 (w) 
0 (mod 3)}. Construct a DFA for h-1 (L).
8. Draw the table of distinguishabilities for the DFA below (run the TF algorithm), and then construct the minimum state equivalent DFA.
|
|
0 |
1 |
|
|
B |
E |
|
B |
C |
F |
|
* C |
D |
H |
|
D |
E |
H |
|
E |
F |
I |
|
* F |
G |
B |
|
G |
H |
B |
|
H |
I |
C |
|
* I |
A |
E |
9. Find minimal DFA’s for the following languages. In each case prove (!) that your DFA is minimal.
(a) {an bm : n e 2, m e 1}
(b) {an : n e 0, n > 3}
2023-05-02