Correct hierarchical relationship among context free, rightlinear, and contextsensitive language is
A.  contextfree ⊂ rightlinear ⊂ contextsensitive 
B.  contextfree ⊂ contextsensitive ⊂ rightlinear 
C.  contextsensitive ⊂ rightinear ⊂contextfree 
D.  rightlinear ⊂contextfree ⊂contextsensitive 
Option: D Explanation : 
In the following grammar :
x : : = x ⊕ y  4
y : : = z * y I 2
z : : = id
which of the folowing is true ?
A.  ⊕ is left associative while * is right associative 
B.  Both ⊕ and * are left associative 
C.  ⊕ is right associative while * is left associative 
D.  None of these 
Option: B Explanation : 
Which of the following CFG's can't be simulated by an FSM ?
A.  S > Sa  b 
B.  S > aSb  ab 
C.  S > abX, X > cY, Y > d  aX

D.  None of these 
Option: B Explanation : Option (b) generates the set {a^{n} b^{n} ,n=1,2,3 ....}which is not regular ,Option (a) is left linear where as option (C) is right linear . 
ADG is said to be in Chomsky Form (CNF), if all the productions are of the form A > BC or
A > a. Let G be a CFG in CNF. To derive a string of terminals of length x , the number of productions to be used is
A.  2x  1 
B.  2x 
C.  2x + I 
D.  None of these 
Option: A Explanation : 
Which of the following statements is correct?
A.  A = { If a^{n} b^{n}  n = 0,1, 2, 3 ..} is regular language 
B.  Set B of all strings of equal number of a's and b's deines a regular language 
C.  L (A* B*)∩ B gives the set A 
D.  None of these 
Option: C Explanation :
If we include A and B in a set and if we write A* it means except then A i.e. B same as B* means except then B i.e.A so if we intersect (A*B*) and B then get A because in any regular language
if we write AB then AB=A intersection B' so if we intersect A and B means AB So intersection of (A*B*) and B = (BA) intersection B means (BA)B' and B'=A so (BA) intersection(A)=A
So ans is (C)

Syllabus covered in this section is
This Section covers Theory of Computation Questions Answers .These questions can be used for the preparation of various competitive and academic exams like
Who can benefit
Various Search Terms Used For This Section Are