Solutions -- formal languages and theory of computation, part 1, CS 288,
May 1, 2006

 

    1. this is undecidable by Rice's Theorem
    2. this is trivially true, since every regular language is context-free
    3. this is decidable, for example by finding a DFA M accepting L(r), and then running M on x.
    4. this is decidable, for example by eliminating useless symbols from G, constructing an accessibility graph for G (whose nodes are G's nonterminals, and for which (A,B) is an edge iff A =*> αBβ for some α and β), and determining whether this graph has a cycle.

  2. An argument that does not involve the pumping lemma runs as follows: Suppose that L is accepted by some DFA M. Since M has only finitely many states, there must be nonnegative integers m and n such that δ(q0, 0m) = δ(q0, 0n). Suppose that this common destination state is called q. Then δ(q, 1m) must be an accepting state, so that 0m1m is accepted. On the other hand, this state must not be an accepting state, lest 0m1n be accepted. This contradiction shows that no DFA M can accept L.

    1. In the set of nonterminals that derive strings of terminals, we may first include B and C, then D, then S and E, and finally H. We may eliminate the other nonterminals A and F from the grammar to get
         S → CD | DE
   B → b | bB
   C → c | cC
   D → dC
   E → eD | De
   H → gE | Eg
      Now in the set of accessible nonterminals, we may first include S, then C and D and E. No other nonterminals are accessible, so the final grammar has productions 
         S → CD | DE
   C → c | cC
   D → dC
   E → eD | De

    2. Since L(G) is generated by the grammar above (with no useless symbols), we may inspect this grammar to answer the question about L(G). The strings that C, D, and E generate can be represented by the respective regular expressions cc*, dcc*, and edcc* + dcc*e. So the grammar does generate a regular language -- one that corresponds to the regular expression cc*dcc* + dcc*(edcc* + dcc*e).