# Theory of Computation MCQ (Multiple Choice Questions) - SchoolingAxis

1. Finite state machine are not able to recognize Palindromes because:

a. Finite automata cannot deterministically find the midpoint

b. Finite automata cannot remember arbitarily large amount of data

c. Even if the mid point is known, it cannot find whether the second half matches the first

d. All of the mentioned

Ans- d. All of the mentioned

2. Which of the following are related to tree automaton?

a. Myphill Nerode Theorem

b. State machine

c. Courcelle's Theorem

d. All of the mentioned

Ans- d. All of the mentioned

3. Myphill Nerode does the following:

a. Minimization of DFA

b. Tells us exactly when a language is regular

c. Both (a) and (b)

d. None of the mentioned

Ans- c. Both (a) and (b)

4. If L is DFA-regular, L' is

a. Non regular

b. DFA-regular

c. Non-finite

d. None of the mentioned

Ans- b. DFA-regular

5. Which of the following are non regular?

a. The set of strings in {a,b}* with an even number of b's

b. The set of strings in {a, b, c}* where there is no c anywhere to the left of a

c. The set of strings in {0, 1}* that encode, in binary, an integer w that is a multiple of 3. Interpret the empty strings e as the number 0.

d. None of the mentioned

Ans- d. None of the mentioned

6. Which of the technique can be used to prove that a language is non regular?

a. Ardens theorem

b. Pumping Lemma

c. Ogden's Lemma

d. None of the mentioned

Ans- b. Pumping Lemma

7. Statement: Left most derivations are lengthy as compared to Right most derivations. Choose the correct option:

a. correct statement

b. incorrect statement

c. may or may not be correct

d. depends on the language of the grammar

Ans- c. may or may not be correct

8. Choose the incorrect process to check whether the string belongs to the language of certain variable or not?

a. recursive inference

b. derivations