Automata Theory Questions and Answers – Testing Emptiness and Membership

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

Answer: c
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

Answer: d
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

Answer: d
Explanation: Membership is a decision property of language class while others mentioned like Kleene, Reversal and Homomorphism are Closure properties of language class.
advertisement
advertisement

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

Answer: d
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

Answer: d
Explanation: It is possible to convert from one specification to another. We can express a regular language in all the given four variants.
Note: Join free Sanfoundry classes at Telegram or Youtube

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

Answer: d
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

Answer: c
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.
advertisement

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

Answer: d
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

Answer: d
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).
advertisement

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

Answer: a
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.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.