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

1. Find a regular expression for a grammar which generates a language which states : L contains a set of strings starting wth an a and ending with a b, with something in the middle.

a. a(a*Ub*)b

b. a*(aUb)b*

c. a(a*b*)b

d. None of the mentioned

Ans- a. a(a*Ub*)b

2. If the partial derivation tree contains the root as the starting variable, the form is known as:

a. Chomsky hierarchy

b. Sentential form

c. Root form

d. None of the mentioned

Ans- b. Sentential form

3. There exists a Context free grammar such that: X->aX; Which among the following is correct with respect to the given assertion?

a. Left Recursive Grammar

b. Right Recursive Grammar

c. Non Recursive Grammar

d. None of the mentioned

Ans- b. Right Recursive Grammar

4. Context free grammar is called Type 2 grammar because of ______ hierarchy.

a. Greibach

b. Backus

c. Chomsky

d. None of the mentioned

Ans- c. Chomsky

5. The following denotion belongs to which type of language: G=(V, T, P, S)

a. Regular grammar

b. Context free grammar

c. Context Sensitive grammar

d. All of the mentioned

Ans- b. Context free grammar

6. abb*c denotes which of the following?

a. {abnc|n=0}

b. {abnc|n=1}

c. {anbc|n=0}

d. {abcn|n>0}

Ans- b. {abnc|n=1}

7. Which of the following strings is not generated by the given grammar: S->SaSbS|e

a. aabb

b. abab

c. abaabb

d. None of the mentioned

Ans- d. None of the mentioned

8. Which of the following regular expression allows strings on {a,b}* with length n where n is a multiple of 4.

a. (a+b+ab+ba+aa+bb+aba+bab+abab+baba)*

b. (bbbb+aaaa)*

c. ((a+b)(a+b)(a+b)(a+b))*

d. None of the mentioned

Ans- c. ((a+b)(a+b)(a+b)(a+b))*

9. Which of the following strings do not belong the given regular expression? : (a)*(a+cba)

a. aa

b. aaa

c. acba

d. acbacba

Ans- d. acbacba

10. Which of the following is an incorrect regular expression identity?

a. R+f=R

b. eR=e

c. Rf=f

d. None of the mentioned

Ans- b. eR=e

11. Which of the following are non essential while simplifying a grammar?

a. Removal of useless symbols

b. Removal of unit productions

c. Removal of null production

d. None of the mentioned

Ans- d. None of the mentioned

12. Statement 1: Ambiguity is the property of grammar but not the language. Statement 2: Same language can have more than one grammar.  Which of the following options are correct with respect to the given statements?

a. Statement 1 is true but statement 2 is false

b. Statement 1 is false but statement 2 is true

c. Both the statements are true

c. Both the statements are false

Ans- c. Both the statements are true

13. Let G=(V, T, P, S); where a production can be written as: S->aAS|a and A->SbA|ba|SS ; Which of the following string is produced by the grammar?

a. aabbaab

b. aabbaa

c. baabab

d. None of the mentioned

Ans- b. aabbaa

14. Which among the following is incorrect with reference to a derivation tree?

a. Every vertex has a label which is a terminal or a variable.

b. The root has a label which can be a terminal.

c. The label of the internal vertex is a variable.

d. None of the mentioned

Ans- b. The root has a label which can be a terminal.

15. CFGs are more powerful than:

a. DFA

b. NDFA

c. Mealy Machine

d. All of the mentioned

Ans- d. All of the mentioned

16. A CFG consist of the following elements:

a. a set of terminal symbols

b. a set of non terminal symbols

c. a set of productions

d. all of the mentioned

Ans- d. all of the mentioned