Theory of Computation MCQ with Answers

Theory of Computation MCQ with Answers

41) For which of the following application, regular expressions can not be used ?

Answer is:

Both 1) Designing computers and 2) Designing compilers

42) Consider the following grammar
S --> Ax / By
A --> By/Cw
B --> x / Bw
C--> y
Which of the regular expressions describe the same set of strings as the grammar ?

Answer is:

xw * y + xw * yx + ywx

43) Which of the following statements is (are) correct ?

Answer is:

All of these

44) Which of the following statement is wrong ?

Answer is:

All languages can be generated by context- free grammar

45) Consider a grammar : G = ( { x , y ) , { s , x , y } , p , s) where elements of parse :
S--> x y
S -->y x
x--> x z
x--> x
y--> y
z--> z
The language L generated by G most accurately is called

Answer is:

Chomsky type 3

6
7
8
9
10
11
12