First time here? Checkout the FAQ!
0 votes

Whats The Answer & How to solve such kind of Questions ?


asked in Theory of Computation by (167 points)   | 43 views
Try to find out counter example for each of option given
if u found any counter eg then eliminate that option
This approach will be helpful

for e.g  option a says string that do not contain bbb but this CFG generates string with bbb as substring inside it
Okay !!

Is it possible to Convert this Grammar to DFA? (If yes , How?)
Since given grammer is CFG you can't make a DFA out of it
But you can make regular expression from it which can help you answer the question but that might took some time :D
Oh right right !!
I forgot Its  a CFG so can't be converted to DFA
Thanks For the help :)

1 Answer

+1 vote
First they should have to mentioned start state here I assuming X as a start state because x is only state from which all other state are reachable, minimum length string generate by x is a


Y-> A from here itself we can say answer is b

Now state X and Y assure that already one a is extra either at beginning or end or both side

State S,A,B ensure number of a= number of b

S,A,B cannot be reached without X hence option b is correct
answered by Boss (6.7k points)  

Top Users Aug 2017
  1. Bikram

    5272 Points


    4730 Points

  3. akash.dinkar12

    3514 Points

  4. manu00x

    3492 Points

  5. rahul sharma 5

    3188 Points

  6. makhdoom ghaya

    2700 Points

  7. just_bhavana

    2432 Points

  8. stblue

    2244 Points

  9. Tesla!

    2090 Points

  10. pawan kumarln

    1876 Points

25,071 questions
32,226 answers
30,232 users