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 : Click on Discuss to view users comments. 
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 : Click on Discuss to view users comments. Preeti said: (4:23am on Thursday 21st November 2013)
Answer A is correct.
anita said: (11:20pm on Tuesday 2nd May 2017)
ans a is correct
Ankit said: (11:42am on Thursday 24th August 2017)
A answer is correct

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 . Click on Discuss to view users comments. 
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 : Click on Discuss to view users comments. kavita said: (11:11pm on Sunday 9th June 2013)
why option a?
Akhil Babu said: (6:55am on Tuesday 27th February 2018)
So in each step when we try to derive a string, there are two possibilities1) Either at every step we are increasing number of variables(Non terminals) by 12) OR we are going to increase number of terminals by 1Therefore we first try to get string of variables whose length is equal to the given string, in this procedure the number of steps required = n1 and from there on we keep on replacing every variable with a terminal, in this procedure the number of steps requires =nSo total = n 1 n =2*n1 steps

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)
Click on Discuss to view users comments. Abdul said: (9:46am on Wednesday 7th December 2016)
What if A does not contain the empty string?

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