I have the following question and its solution enter image description here

Here T -> XTX since T -> X and X->b S ->XbX since X->a S->aba

So,why is option 3 not accepted ?

  • $\begingroup$ Take a look at the CYK-Algorithm , it is a very mechanical algorithm for checking if a word belongs to a CFG. Perfectly used when you get stuck in interpeting a CFG. $\endgroup$ – JohEker Nov 13 '18 at 12:29
  • $\begingroup$ @JohEker will take a look at that.Thanks $\endgroup$ – techno Nov 13 '18 at 14:31

Read the question again, this time focus better. Take the grammar of the question, not the grammar in your mind.

I only need to see the rules for S to know that the strings in (3) are not part of the language.

S is the start symbol. Look at the rules for S. Think why I'm saying that aba and aa cannot possibly be in the language, without me having to look at any other rules whatsoever. You should be able to say "Looking at the rules for S, it is obvious that all strings in the language either xxx or yyy".

  • $\begingroup$ Can you tell me why my approach is wrong ? $\endgroup$ – techno Nov 13 '18 at 11:55
  • $\begingroup$ @techno What exactly was your approach? $\endgroup$ – ttnick Nov 13 '18 at 13:50
  • $\begingroup$ I think the approach was using rules that are not quite the rules in the grammar. $\endgroup$ – gnasher729 Nov 13 '18 at 14:30
  • $\begingroup$ @PHPNick I failed to start with the start symbol. $\endgroup$ – techno Nov 13 '18 at 14:30
  • $\begingroup$ On what basis do you say that S is the start symbol? If R is not the start symbol, it's useless, although useless non-terminals are completely legit. But the definition of G should be explicit IMHO. Also, what's wrong wirh answering (d)? Those sentences cannot be generated by R or S either. It seems to me that it's really not a very good test question. $\endgroup$ – rici Nov 14 '18 at 3:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.