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 M1=(Q,Σ,δ1,q0,F) and M2=(R,Σ,δ2,r0,G) that recognize regular languages A1 and A2, respectively, construct a DFA D that recognizes A1 - A2.