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

1. The difference between number of states with regular expression (a + b) and (a + b)* is:

a. 1

b. 2

c. 3

d. 0

Ans- a. 1

2. Arden's theorem is true for:

a. More than one initial states

b. Null transitions

c. Non-null transitions

d. None of the mentioned

Ans- c. Non-null transitions

3. A finite automaton accepts which type of language:

a. Type 0

b. Type 1

c. Type 2

d. Type 3

Ans- d. Type 3

4. RR* can be expressed in which of the forms:

a. R+

b. R-

c. R+ U R-

d. R

Ans- a. R+

5. Concatenation of R with ? outputs:

a. R

b. ?

c. R.?

d. None of the mentioned

Ans- b. ?

6. Concatenation Operation refers to which of the following set operations:

a. Union

b. Dot

c. Kleene

d. Two of the options are correct

Ans- b. Dot

7. Which among the following looks similar to the given expression? ((0+1). (0+1))*

a. {x? {0,1} *|x is all binary number with even length}

b. {x? {0,1} |x is all binary number with even length}

c. {x? {0,1} *|x is all binary number with odd length}

d. {x? {0,1} |x is all binary number with odd length}

Ans- a. {x? {0,1} *|x is all binary number with even length}

8. Which of the following does not represents the given language? Language: {0,01}

a. 0+01

b. {0} U {01}

c. {0} U {0}{1}

d. {0} ^ {01}

Ans- d. {0} ^ {01}

9. A language can be generated from simple primitive language in a simple way if and only if

a. It is recognized by a device of infinite states

b. It takes no auxiliary memory

c. Both are correct

d. Both are wrong

Ans- b. It takes no auxiliary memory

10. L is a regular Language if and only If the set of ____ classes of IL is finite.

a. Equivalence

b. Reflexive

c. Myhill

d. Nerode

a. Equivalence