Theory of Computation MCQ with Answers

Theory of Computation MCQ with Answers

46) Consider a grammar : G = { { S } , { 0 , 1 } , p , s } where elements of p are:
S --> ss
S--> 0S1
S--> 1S0
S--> empty
The grammar will generate

Answer is:

regular language

47) A grammar that produces more than one parse tree for some sentence is called

Answer is:

ambiguous

48) Given a grammar G a production of G with a dot at some position of the right side is called

Answer is:

LR (0) item of G

49) If a language is denoted by a regular expression L = ( x )* (x | y x ) , then which of the following is not a legal string within L ?

Answer is:

x y x y x

50) If every string of a language can be determined, whether it is legal or illegal in finite time, the language is called

Answer is:

decidable

7
8
9
10
11
12
13