This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses 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
View Answer
Explanation: 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
View Answer
Explanation: 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
View Answer
Explanation: 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
View Answer
Explanation: 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
View Answer
Explanation: 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
View Answer
Explanation: 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) Helps construct representations and shows informally described languages not to be in class
d) None of the mentioned
View Answer
Explanation: 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) 5
View Answer
Explanation: If a string belongs to a language, the number of steps required to test that membership 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
View Answer
Explanation: 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
View Answer
Explanation: This occurs because there are atleast n+1 states along the path while traversing the string w.
Sanfoundry Global Education & Learning Series – Automata Theory.
To practice all areas of Automata Theory, here is complete set of 1000+ Multiple Choice Questions and Answers.
- Practice Computer Science MCQs
- Apply for Computer Science Internship
- Check Automata Theory Books
- Check Computer Science Books