First time here? Checkout the FAQ!
0 votes

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


asked in Theory of Computation by (455 points) 6 | 60 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 (9.5k points) 5 29 58

Related questions

+1 vote
1 answer
0 votes
0 answers
asked in Theory of Computation by manu00x Veteran (14.9k points) 6 19 58 | 51 views
+1 vote
0 answers
asked in Theory of Computation by iarnav Loyal (4.6k points) 4 38 112 | 45 views

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Top Users Oct 2017
  1. Arjun

    23324 Points

  2. Bikram

    17048 Points

  3. Habibkhan

    7808 Points

  4. srestha

    6222 Points

  5. Debashish Deka

    5430 Points

  6. jothee

    4958 Points

  7. Sachin Mittal 1

    4772 Points

  8. joshi_nitish

    4286 Points

  9. sushmita

    3964 Points

  10. Rishi yadav

    3794 Points

Recent Badges

Notable Question makhdoom ghaya
Popular Question LavTheRawkstar
Avid Voter atul_21
Popular Question hem chandra joshi
100 Club nikhil_cs
Notable Question Sukannya
Notable Question Sourabh Kumar
Notable Question shikharV
Nice Comment Sachin Mittal 1
Popular Question ManojK
27,287 questions
35,134 answers
33,223 users