Exam 1 Study Guide
The first exam will cover the regular-"world": DFA's, NFA's, regular expressions, and the pumping lemma. Examples in this webpage come from our textbook (Sipser).
Read all of Chapter 1 in the textbook.
Some questions you will be asked to solve on the exam are:
- Create NFA's from regular expressions. You will be required to chain together smaller NFA's such as in Examples 1.56 and 1.58 (see pages 68 and 69 in the textbook). Study Exercise 1.28 on page 88.
- Convert an NFA to a DFA. Study Exercise 1.16 on page 86.
- Understand the pumping lemma and pumping length. Prove a language is not regular using the pumping lemma. Study Exercise 1.29 on page 88. Find the pumping length of languages by solving Problem 1.55 on page 91.
- Draw a DFA for a given regular language. Study Exercise 1.6 on page 84. (Advanced: draw a DFA for Problem 1.48).
- Convert an NFA to a regular expression (showing all the GNFA steps). Study Exercise 1.21 on page 86. An additional example is here.
- Show that regular languages are closed under some operation. See Theorems 1.45, 1.47, and 1.47 on pages 59 to 62. Solve Problem 1.70 on page 93.
Additional practice:
- Convert the following NFA to a regular expression (draw each GNFA). Also, try converting it to a DFA.
- For each regular language, what is its minimum pumping length?
- L = {a,aa,bab,aaaaa}
- L = {1111,2,3,4*,5}
- L = a(abc)*
- L = {w : w ends with aba over the alphabet {a,b}*}
- L = (xxx)*(yy)*
- Convert the regular expression ((0 | (1*01*))(001)*)* to an NFA. Show the detailed, step-by-step process of building smaller NFA's and combining them using the union, star, and concatenation operations.
- Prove that regular languages are closed under reversal by constructing (drawing) a high-level diagram of an NFA and carefully explaining what changes occur to the NFA in order to make the machine recognize the reverse language. That is, show that if L is regular then LR is regular.