MCQ Computer Science

# Automata Theory Multiple Choice Quaestion & Answers (MCQs) set-20

1. What kind of expressions do we used for pattern matching?
a) Regular Expression
b) Rational Expression
c) Regular & Rational Expression
d) None of the mentioned

Explanation: In automata theory, Regular Expression(sometimes also called the Rational Expression ) is a sequence or set of characters that define a search pattern, mainly for the use in pattern matching with strings or string matching.

2. Which of the following is true?
a) (01)*0 = 0(10)*
b) (0+1)*0(0+1)*1(0+1) = (0+1)*01(0+1)*
c) (0+1)*01(0+1)*+1*0* = (0+1)*
d) All of the mentioned

Explaination : None.

3. Generate the regular expression to match blank lines
a) / */
b) /bl
c) /^?/
d) /^\$/

Explanation: There are few expressions which provide the utility of matching metacharacters including /^\$/ for blank lines, / */ for matching one or more spaces, /^.*\$/ for matching an entire line whatever it is.

4. State true or false:
Statement: A lexical analyzer reads the source code line by line.
a) True
b) False

Explanation: A lexical analyzer reads the source code letter by letter and when it encounters a space or an operator or any special character, it decides that the word is completed.

5. If L is DFA-regular, L’ is
a) Non regular
b) DFA-regular
c) Non-finite
d) None of the mentioned

Explanation: This is a simple example of a closure property: a property saying that the set of DFA-regular languages is closed under certain operations.

6. Which among the following can be an annihilator for multiplication operation?
a) 0
b) 1
c) 100
d) 22/7

Explanation: An annihilator for an operator is a value such that when the operator is applied to the annihilator and some other value, the result is the annihilator.

7. Answer in accordance to the third and last statement in pumping lemma:
For all _______ xyiz ?L
a) i>0
b) i<0
c) i<=0
d) i>=0

Explanation: Suppose L is a regular language . Then there is an integer n so that for any x?L and |x|>=n, there are strings u,v,w so that
x= uvw
|uv|<=n
|v|>0
for any m>=0, uvmw ?L.

8. Which of the following is not an application of Pumping Lemma?
a) {0i1i|i>=0}
b) {0ix|i>=0, x?{0, 1}* and |x|<=i}
c) {0n| n is prime}
d) None of the mentioned

Explanation: None of the mentioned are regular language and are an application to the technique Pumping Lemma. Each one of the mentioned can be proved non regular using the steps in Pumping lemma.

9. If L is a regular language, then (((L’)r)’)* is:
a) regular
b) non regular
c) may be regular
d) none of the mentioned

Explanation: If L is regular so is its complement, if L’ is regular so is its reverse, if (L’)r is regular so is its Kleene.

10. Which of the following is a correct statement?
a) Moore machine has no accepting states
b) Mealy machine has accepting states
c) We can convert Mealy to Moore but not vice versa
d) All of the mentioned

Explanation: Statement a and b is correct while c is false. Finite machines with output have no accepting states and can be converted within each other.

11. Which one among the following is true?
A mealy machine
a) produces a language
b) produces a grammar
c) can be converted to NFA
d) has less circuit delays

Explanation: It does not produce a language or a grammar or can be converted to a NFA.

12. If we select a string w such that w?L, and w=xyz. Which of the following portions cannot be an empty string?
a) x
b) y
c) z
d) all of the mentioned

Explanation: The lemma says, the portion y in xyz cannot be zero or empty i.e. |y|>0, this condition needs to be fulfilled to check the conclusion condition.

13. Pigeonhole principle can be applied in the following computer science algorithms:
a) hashing algorithm
b) lossless compression algorithm
c) both (a) and (b)
d) none of the mentioned

Explanation: Collisions are inevitable in a hash table because the number of possible keys exceeds the number of indices in the array.

14. Which among the following are the boolean operations that under which regular languages are closed?
a) Union
b) Intersection
c) Complement
d) All of the mentioned

Explanation: Regular languages are closed under the following operations:
a) Regular expression operations
b) Boolean operations
c) Homomorphism
d) Inverse Homomorphism

15. If L is a regular language, ____ is also regular.
a) Lr
b) L’
c) L*
d) All of the mentioned