## Ars Digita University

Theory of Computation

Recitation 4, 05/08/01

## 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 }

Dimitri Kountourogiannis, dimitrik@alum.mit.edu