Theory of Computation

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 espilon transitons 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 }

 

Topics

• Decision Problems
• Context free grammars.

Problems to work on

Decision Problems

1. Finish the decision problems form the last recitation handout.

CFG warmup

2. Give a context free grammar that generates the language of palindromes {w(0+1+epsilon)w^R| w is in (0 + 1)*}
3. Give a context free grammar that generates every possible string over {0,1}
4. Give a context free grammar that generates the language 0ⁿ1 0ⁿ111 0^m 1^r where n, m, r >= 0
5. Give a context free grammar that generates the language of all strings that contain 101.
6. Give a context free grammar that generates the language of all strings with an equal number of zeros and ones.

And/Or

7. Give a context free grammar that generates the language that has equal numbers of 0’s and 1’s or contains 101.
8. Give a context free grammar that generates the language that has equal numbers of 0’s and 1’s and contains 101.

Complements

9. Give a context free grammar that generates the language of all strings of the form 0^m1ⁿwhere n >= m >= 0.
10. Give a context free grammar that generates the language of all strings of the form 0^m1ⁿwhere n > m >= 0.
11. Give a context free grammar that generates the complement of the language 0*1*.
12. Give a context free grammar that generates the language { w | w is not equal to 0ⁿ1ⁿfor any choice of n}
13. Challenging problem: Give a context free grammar that generates the language { w | w is not a palindrome}