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.6k points)   | 130 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 (599 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 May 2017
  1. akash.dinkar12

    3338 Points

  2. pawan kumarln

    2066 Points

  3. Bikram

    1922 Points

  4. sh!va

    1672 Points

  5. Arjun

    1614 Points

  6. Devshree Dubey

    1272 Points

  7. Debashish Deka

    1174 Points

  8. Angkit

    1056 Points

  9. LeenSharma

    1018 Points

  10. Arunav Khare

    758 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 May 22 - 28
  1. Bikram

    1008 Points

  2. pawan kumarln

    692 Points

  3. Arnab Bhadra

    632 Points

  4. Arjun

    342 Points

  5. bharti

    328 Points

22,888 questions
29,193 answers
27,691 users