Theory of Computation MCQ with Answers

Theory of Computation MCQ with Answers

26) If L1 and L2 are context free language and R a regular set, then which one of the languages below is not necessarily a context free language?

Answer is:

L1 ∩L2

27) Consider a grammar with the following productions
S--> aab | bac | aB
S --> αS | b
S --> αb b | ab
Sα --> bdb | b
The above grammar is

Answer is:

context sensitive

28) What can be said about a regular language L over {a} whose minimal finite state automation has two states?

Answer is:

L must be {an |n is even}

29) In a context-sensitive grammar, number of grammar symbols on the left hand side of a production can't be greater than the number of

Answer is:

non-terminals on the right hand side

30) In a context-free grammar

Answer is:

all of these

3
4
5
6
7
8
9