## Ars Digita University

Theory of Computation

Recitation 5 , 05/09/01

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

Dimitri Kountourogiannis, dimitrik@alum.mit.edu