**Topics**

- How to minimize DFA’s and why one would.
- Turning a DFA into a Grammar
- Decision Problems.
- Some applications of Regular expressions
- Everything is a string / number.

**Problems to work on**

- Why do we care about minimizing DFA’s ?
- Minimize the following DFA. What Language does it generate?
- Minimize the following DFA. What Language does it generate?
- Minimize the following DFA. What Language does it generate?
- Give a regular grammar that generates the same language as the DFA in problem 2.
- Give a regular grammars that generates the same language as the following regular expressions:
- 010*
- a(ab + bc)*

- Is the following a valid argument? Why or why not? The language L = {0
^{m}1^{m}2^{n}| m, n >= 0 } is not regular, since we already know that M = { 0^{m}1^{m}| m >= 0} is not regular by the pumping lemma, and since L contains M it cannot therefore be regular. - Prove that the language { x
^{2n}| n >= 0 } is not regular. - Give a decision algorithm which takes as input a regular language L and decides whether L contains the string 1000101.
- Give a decision algorithm which takes as input a regular language L and decides whether L equals the language {1000101}
- Give a decision algorithm which takes as input a regular language L and decides whether L contains the language given by the regular expression 10*10*1
- Miscellaneous problem: Eliminate the espilontransitons of this NFA, without converting it to a DFA (ie, figure out an easier way)
- Mildy Challenging and Surprising Problem: Let L be any language over the alphabet {0}, not necessarily regular. Show that L* is regular.
- Wicked hard challenging problem: Describe a grammar that generates the language { 0
^{p}| p is a prime }

Last Updated on