Solutions -- formal languages and theory of computation, part 1, CS 288,
April 30, 2007

 

  1. A minimal DFA is given below. There are other, nonminimal DFAs that will work.

    One way of attaining the given answer is to start with the ε-NFA below, where the unlabeled edge represents an ε-move.

     

    1. It is always possible to remove ε-productions from a CFG G, unless ε is in L(G). If ε is in L(G), then some ε-production must remain to allow the start symbol S to derive ε.
    2. The nullable symbols are B, C, and E.
    3. One equivalent grammar without ε-productions has start symbol S and productions
            S → a | aB | aC | aBC | bD | bCD | e | eE | aA
            A → a | aa | aaB
            B → b | bB 
            C → D | CD
            D → d | dD
            E → e | B | C | BC

     

    1. Decidable. One can find an equivalent DFA M' for r (perhaps going through intermediate stages of an ε-NFA and an NFA), minimize both M and M', and check whether M and M' are isomorphic..
    2. Trivially decidable, since the answer is always "yes". Don't confuse the algorithm that takes a CFG G and determines whether L(G) is recursive with the algorithm that takes a CFG G and a string x and determines whether G generates x. The first algorithm always answers "yes", the second one may answer "no". However the existence of the second algorithm is enough to show that the first algorithm always answers "yes", even though it's not the second algorithm that decides whether a given CFL is recursive.
    3. Undecidable by Rice's theorem.
    4. Decidable. One can use an algorithm of the Hopcroft et al text to determine whether the start symbol of G is a generating symbol.