Practice 1

This practice is for big quiz 1. The set of questions below is not an example of a quiz for 1 hour. There will be only 3-4 questions on the quiz.

แบบฝึกหัดด้านล่างมีไว้สำหรับเตรียมพร้อมสำหรับ big quiz 1. อย่างไรก็ตาม จำนวนข้อในแบบฝึกหัดมีมากกว่าที่จะทำได้ใน 1 ชั่วโมง. ใน quiz น่าจะมีประมาณ 3-4 ข้อ.

1. Find a DFA for the language { w | w contains at least two 0's and at most one 1 }. (1.6j)
2. Find a DFA for the language { w | w doesn't contain the substring 110 }. (1.6f)
3. Find a DFA for the language { w | w is a binary number divisible by 5 }
4. Do exercise 1.16.
5. Convert the regular expression (0 ∪ 1)^*000(0 ∪ 1)^* to an NFA. (1.18)
6. Prove that every NFA can be converted to an equivalent one that has a single accept state. (1.11)
7. Given DFA's M₁=(Q,Σ,δ₁,q₀,F) and M₂=(R,Σ,δ₂,r₀,G) that recognize regular languages A₁ and A₂, respectively, construct a DFA D that recognizes A₁ - A₂.