First time here? Checkout the FAQ!
+2 votes

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.
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

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
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

    1084 Points

  7. Hemant Parihar

    1050 Points

  8. Shubhanshu

    978 Points

  9. Ahwan

    876 Points

  10. akash.dinkar12

    652 Points

23,958 questions
30,901 answers
29,277 users