Theory of Computation - Context free languages
3. Which of the following CFG's can't be simulated by an FSM?
- Option : B
- Explanation : Option (B) generates the set {an bn, n=1,2,3 ....} which is not regular, Option (A) is left linear where as option (C) is right linear .
5. Which of the following statements is correct?
- 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 A-B then A-B=A intersection B' so if we intersect A and B means A-B 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)
