Automata Theory Multiple Choice Questions on “Testing Emptiness and Membership”.
1. Language classes have the following property:
a) Closure property
b) Decision property
c) Closure & Decision property
d) None of the mentioned
Answer: c
Clarification: A decision property of a language class is an algorithm that takes a formal description of a language(e.g., a DFA) and tells whether or not some property holds.
2. Which of the following are decision properties?
a) Emptiness
b) Infiniteness
c) Membership
d) All of the mentioned
Answer: d
Clarification: Emptiness, Infiniteness and Membership are the decision properties of any language class. Example: Is the language L empty? Or Is w, a string belongs to the regular language L?
3. Pick the odd one out of the given properties of a regular language:
a) Kleene
b) Reversal
c) Homomorphism
d) Membership
Answer: d
Clarification: Membership is a decision property of language class while others mentioned like Kleene, Reversal and Homomorphism are Closure properties of language class.
4. For an automata, which of the following are equivalent variants?
DFA,NFA and NFA with epsilon transitions
a) DFA and NFA
b) NFA and epsilon NFA
c) DFA and epsilon NFA
d) All of the mentioned
Answer: d
Clarification: For a given automata, all the formats of representation be it deterministic finite automata or non deterministic finite automata or non deterministic finite automata with epsilon transitions, all are equivalent variants.
5. Which of the following are not meant to specify a regular language?
a) Regular Expression
b) DFA
c) NDFA and epsilon-NFA
d) All of the mentioned
Answer: d
Clarification: It is possible to convert from one specification to another. We can express a regular language in all the given four variants.
6. Which of the following problems do not belong to decision properties?
a) Given two languages, are there strings that are in both
b) Is the language a subset of another regular language
c) Is the language same as another regular language
d) None of the mentioned
Answer: d
Clarification: To give a solution to the mentioned problems, we require decision properties and for some, we need additional tools like minimized automaton and Pumping lemma.
7. Which of the following is a function of Closure properties?
a) Helps construct representations
b) Helps show informally described languages not to be in class
c) Both (a) and (b)
d) None of the mentioned
Answer: c
Clarification: Using closure properties we can give a=solution to many problems like :
Is the regular languages L1 and L2 closed on concatenation operation?, etc.
8. Suppose there is a string w=abbab, and there exists a DFA which accepts w. How many stepts will be required to test its membership?
a) 2
b) 1
c) 4
d) None of the mentioned
Answer: If a string belongs to a language, the number of steps required to test that member ship is equal to the length of string i.e. 5.
9. If a DFA has n states and the language contains any string of length n or more, the language is termed as:
a) Infinite
b) Empty
c) Non regular
d) None of the mentioned
Answer: The language is surely finite if it is limited to string of length n or less. This is because there are atleast n+1 states along the path while traversing w(string).
10. State true or false:
Statement: If an n-state DFA accepts a string w of length n or more, then there must be a state that appears twice on the path labeled w from the start state to the final state.
a) true
b) false
Answer: a
Clarification: This occurs because there are atleast n+1 states along the path while traversing the string w.