CS341 Automata TheorySummer 2008Midterm Practice Problems1. Define a deterministic finite automaton for the following languages:(a) L = {w ∈ {0 , 1, ...9}∗|w represents an odd natural number with no leading 0s}(b) L = {w ∈ {0, 1, 2}∗|w does not end in 12}(c) L = {w ∈ {a, b}∗|w contains the string aba or w does not contain aa}2. Define an NFA that recognizes the following languages:(a) L = {w ∈ {a, b}∗|w contains at least one instance of abaa, abbb, or baab}(b) L = {anbam|n, m ≥ 0, n ≡3m}(c) L = {w ∈ {a, b, c}∗|w contains substring abb and substring bbc}3. Describ e concisely the language described by the r egular expression.(a) (a∗a)b ∪ b(b) (a∗b∗)∗ab ∪ (a∗b∗)∗ba(b ∪ a)∗4. Write a regular expression that represents the following languages.(a) L = {w ∈ {a, b}∗|#a(w) ≤ 5}(b) L = {w ∈ {a, b}∗|#a(w) ≡30}(c) L = {w ∈ {a, b}∗|w contains exactly one occurrence of string aa}5. Use the algorithm presented in class to convert the regular expression (0∪1)∗000(0∪1)∗to an NFA.6. Convert the following finite automaton to a regular expression using the algorithmgiven in class.1ababbaba12 347. 1.29 in Sipser8. 1.30 in Sipser9. 1.40a in Sipser10. 1.46bd in Sipser11. True or False:(a) The union of an infinite number of regular languages is regular.(b) The intersection of an infinite number of regular languages is regular.(c) Every subset of a r egular language is regular.12. 2.3 in Sipser13. 2.414. 2.815. 2.6a16. 2.30abc (Save this one for final exam pra ctice - we haven’t covered the CFL PumpingLemma yet)17.
View Full Document
Unlocking...