theory of computational

“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

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 mentionedAnswer: 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
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.


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