Chapter 4 --- Little Quiz                                                                
1. Which is correct? (a)   Some RL’s cannot be accepted by automata.(b)      It is impossible to test whether two descriptions of RL’s define the same languages.(c) Testing if an RL generated by an automaton is empty is equivalent to testing if there exists no path from the start state to an accepting state.(d) Some RE's cannot be converted into automata.

2. Which is correct? (a)   The problem of testing emptiness of RL’s is undecidable(b)   The problem of testing the membership of an RE is undecidable (c) A DFA M may be minimized to have fewer states than any DFA equivalent to M.(d)  The problem of testing the equivalence of two RL’s is undecidable

3. Which is correct? (a) The pumping lemma for RL’s is used for proving a language to be regular.(b) The closure property of RL’s means a new language coming from an operation on two RL’s is not an RL.(c) The proof technique using the pumping lemma for RL’s is by contradiction.(d) RL’s are not closed under the operation of difference.

4. Which is correct? (a) The language of all strings, each with n 0's followed by n 1's, is a regular language.(b) Most of the decision problems of RL’s are unsolvable.(c) Minimization of a DFA is good for reducing the resources required for implementation of the DFA.(d) Most of the closure properties of RL’s are not true.

5. Which is correct? (a) RL’s are not closed under union, concatenation, and closure operations . (b) The intersection of two RL’s is not an RL. (c) The complement of an RL is an RL.(d) RL’s are not closed under inverse homomorphism.