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.4k points)   | 121 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 (569 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 Feb 2017
  1. Arjun

    5410 Points

  2. Bikram

    4230 Points

  3. Habibkhan

    3952 Points

  4. Aboveallplayer

    3086 Points

  5. Debashish Deka

    2564 Points

  6. sriv_shubham

    2318 Points

  7. Smriti012

    2240 Points

  8. Arnabi

    2008 Points

  9. mcjoshi

    1696 Points

  10. sh!va

    1684 Points

Monthly Topper: Rs. 500 gift card

20,864 questions
26,030 answers
22,144 users