GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
132 views

I belived, 2nd option is correct but GeeksforGeeks anwered it as (iv), how?

asked in Theory of Computation by Veteran (14.7k points)   | 132 views
vijay ii is true
@vijay can u explain what is difference b/w "grammar symbols" [option 2] and "non terminals" [option 4] ?
@ Gate mission 1        Grammar symbol means both "terminal" and "non-terminal" symbol.
Okay.
Option 1 is also correct for CSL. right?
@ jason no, Option 1 is not ryt u can have "epsilon" on right hand side of production
ok!!!

1 Answer

0 votes

In CSL   A -> B  where A belongs to (terminal +non-terminal)and B belongs to (terminal + non-terminal)

and lengthof(A) <=lenghtof(B) (always)

but incase B='epsilon' i dont know whether this condition holds true or not

so answer might be "option 4" possible but i am not sure correct me if i am wrong.

answered by Junior (629 points)  
S->epsilon is nt a valid production in CSG...though epsilon belongs to CSL...
ε is nt a grammar symbol ?
@Saurabh. S->epsilon can't be the production in CSG and the reason lies with simplication of CFG rules where we eliminate epsilon productions.
but my doubt is nt that....
ε is nt a grammar symbol r nt ?
Yes, epsilon isnt a grammar symbol
okk....
Can someone give general production rules for all Grammers ? Like the one given for CSL above ?


Top Users Jul 2017
  1. Bikram

    3782 Points

  2. manu00x

    2464 Points

  3. Debashish Deka

    1832 Points

  4. joshi_nitish

    1494 Points

  5. Arnab Bhadra

    1096 Points

  6. Arjun

    1054 Points

  7. Hemant Parihar

    1050 Points

  8. Shubhanshu

    972 Points

  9. Ahwan

    876 Points

  10. akash.dinkar12

    642 Points


23,953 questions
30,895 answers
70,106 comments
29,272 users