in Theory of Computation
1,284 views
1 vote
1 vote

in Theory of Computation
1.3k views

2 Answers

12 votes
12 votes
Best answer

For a given regular language , we can have both regular and non regular (CFG or CSG) grammar..On similar line , for a given CFL , we can have a CFG and a non CFG too..

Hence there is a possibility that a CFG is equivalent to  a non CFG in this context.Hence 1st statement is correct..

Now 2nd and 3rd statements we have to consider the fact that if a grammar is left and right linear , then it is not regular..So we can say since S --> ab | abc gives a regular grammar[Also if we follow the basic rule of Type 3 grammar we can arrive at the conclusion which is every production in regular langauge should be V --> T* + T*V [Right linear] or V --> T* + VT* [Left linear] but not both.Hence statement 2 is false..

But in 3rd statement in S --> aA the variable is in right side and in S --> Bb the variable is in left most side of RHS of the production.Hence it is both left and right linear and hence not regular also..It is a linear grammar..

Hence A) is the correct answer

selected by

4 Comments

U have misinterpreted the statement..
0
0
i don't understand how first statement is true.Can u give an  example to illustrate the point?
0
0
context free grammar is subset of context senstive language so a cfg can also be a non-cfg too
0
0
0 votes
0 votes
I think 2 only .

1st one is wrong . for CFG equivalent non CFG is not possible
2 is correct
3 we cannot say anything as we need productions of A and B .
by

Related questions