Formal languages and theory of computation, part 1, CS 288, May 1, 2006

Each of the three questions is worth 20 points

For each of the following, state whether the problem is trivial (i.e, has only positive instances or only negative instances), decidable but nontrivial, or undecidable.
1. given a Turing machine M represented as a string of bits, does M accept a context-free language?
2. given a DFA M, does M accept a context-free language?
3. given a regular expression r and a string x, both over an alphabet Σ, is x a member of the language L(r) defined by r?
4. given a CFG G, is L(G) infinite?
Give a one-sentence justification of your answer for each problem.
Let L = {x in {0,1,2}* | x has the same number of 0's as 1's}. Show that L does not equal L(M) for any DFA M. You needn't use the pumping lemma (although you may).
1. (14 points) Find a context-free grammar equivalent to the grammar G below, such that the new grammar has no useless symbols. The symbol S is the start symbol of G.
```
   S → AB | CD | EF | DE
   A → aA | Aa
   B → b | bB
   C → c | cC
   D → dC
   E → eD | De
   F → eA | Ae
   H → gE | Eg 
```
2. (6 points) Is L(G) a regular language? If not, state why not. If so, give a regular expression for L(G).