- Finish building regular expression for language of problem set 1 NFA/DFA
- Build NFA for (a∪b)a*
- Prove that all finite languages are regular
- Let L be finite language { w1, w2, …, wn }
- L described by RE w1 ∪ w2 ∪ … ∪ wn
- What language is described by (a ∪ the) (cat ∪ desk ∪ banana)
(sees ∪ likes ∪ eats) the (big ∪ ε) (tomato ∪ dog)
- So regular expressions can describe at least parts of “real” languages
- Who would have thought definitions of computation had close ties to the structure of natural languages?
- Is it possible that English is actually a regular language? How would we know if it weren’t?
- Languages that aren’t regular
- Example: consider strings of the form anbn
- An automaton to recognize all of them seems to run into problems with finiteness
- Read section 1.4