Formal languages and theory of computation, part 1, CS 288, April 30, 2007

Each of the three questions is worth 20 points

Find a DFA that accepts the language L(r), where r is the regular expression (10)*(12)*. You needn't use any particular algorithm. Your DFA needn't be minimal, but for full credit it must be a DFA and not just an NFA.
Recall that in a CFG, an ε-production is a production in which the right-hand side is empty, and a nullable symbol is a variable symbol that generates the empty string.
1. Under what conditions is it possible to remove ε-productions from a grammar G? That is, under what conditions can a CFG G' be found such that G' has no ε-productions and L(G') = L(G). You should be able to give both necessary and sufficient conditions.
2. If G is the CFG with start symbol S and productions given below, which symbols are nullable in G?
3. Show the result of removing ε-productions from this CFG G.
```
              S → aBC | bCD | eE | aA
              A → a | aaB
              B → ε | bB 
              C → ε | CD
              D → d | dD
              E → e | BC
```
For each of the following questions, state whether or not the question is decidable. Justify your answers in each case. When your answer is yes, giving the name or brief description of an appropriate decision algorithm is sufficient justification. If your decision algorithm invokes another algorithm, you need only specify what this other algorithm does -- you needn't give details of how it works.
1. Given a regular expression r and a DFA M, is L(r) = L(M)?
2. Given a CFG G, is L(G) a recursive language?
3. Given a Turing machine M represented as a string of bits, does L(M) contain the empty string?
4. Given a CFG G, is L(G) empty?