Theory of Computation MCQ with Answers

Theory of Computation MCQ with Answers

6) A class of language that is closed under

Answer is:

both 1) union and complementation has to be closed under intersection and 2) intersection and complement has to be closed under union

7) The productions
E—>E+E
E—>E—E
E-->E*E
E —> E / E
E —> id

Answer is:

generate an ambiguous language but not inherently so

8) Which of the following definitions below generates the same language as L, where
L = {xn yn such that n > = 1} ?
I. E —> xEy | xy
II. xy | (x+ xyy+)
III .x+y+

Answer is:

I only

9) Following context free grammar
S —> aB | bA
A —>b | aS | bAA
B —> b | bS | aBB
generates strings of terminals that have

Answer is:

equal number of a ′s and b ′s

10) Define for the context free language
L< {0;1} init (L) = { u | u v ε L for some v in {0, 1}}
If L { w | w is non-empty and has an equal number of 0's and 1's}, then init (L) is set of all binary strings

Answer is:

including the null string.