Theory of computing

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

1. Why do we care about minimizing DFA’s ?
2. Minimize the following DFA. What Language does it generate?
3. Minimize the following DFA. What Language does it generate?
4. Minimize the following DFA. What Language does it generate?
5. Give a regular grammar that generates the same language as the DFA in problem 2.
6. Give a regular grammars that generates the same language as the following regular expressions:
   1. 010*
   2. a(ab + bc)*
7. Is the following a valid argument? Why or why not? The language L = {0^m1^m2ⁿ | 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.
8. Prove that the language { x²ⁿ| n >= 0 } is not regular.
9. Give a decision algorithm which takes as input a regular language L and decides whether L contains the string 1000101.
10. Give a decision algorithm which takes as input a regular language L and decides whether L equals the language {1000101}
11. 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
12. Miscellaneous problem: Eliminate the espilontransitons of this NFA, without converting it to a DFA (ie, figure out an easier way)
13. Mildy Challenging and Surprising Problem: Let L be any language over the alphabet {0}, not necessarily regular. Show that L* is regular.
14. Wicked hard challenging problem: Describe a grammar that generates the language { 0^p| p is a prime }