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

**Topics**

- Decision Problems
- Context free grammars.

**Problems to work on**

**Decision Problems**

- Finish the decision problems form the last recitation handout.

**CFG warmup**

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

**And/Or**

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

**Complements**

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

Last Updated on February 11, 2019 by Essay Pro