enter image description here

This is taken from a practice quiz by my university.

I ruled out that aabbbaab is not part of the grammar:

S → aSb → aaSbb... This shows that I can't make this word because it would have to have atleast two b's at the end in order for me to add more letters

Then I tried to see if abbaabb can be derived from the grammar and I experienced the same thing:

S → aSb → aaSbb... This shows that I can't make a word with two b's at the end without having at least two a's in the beginning

Finally, I tried to do aabaabbb:

S → aSb → aaSbb → aaSSbb → aaSaSbbb... I decided it can't be this one because even if I make aaSaSbbb into ϵ, I still need to find a way to make aaSaSbbb into ba so I can derive the word. It doesn't seem like I can do that.

So by elimination I thought the correct answer was aabaabb but I was wrong.

Please show me how to work out whether a word can be derived from a grammar.

  • $\begingroup$ The language is a Dyck language. Perhaps if you write a as { and b as }, the pattern will be clearer. $\endgroup$
    – rici
    Mar 2, 2021 at 23:40
  • 1
    $\begingroup$ As a first cut, it's clear that any word derivable in this grammar must have the same number of a's as b's. This eliminates half the possibilities. @rici's answer, of course, is more precise. $\endgroup$ Mar 3, 2021 at 0:41

1 Answer 1


The given grammar

This is what we have at our hand.

Now let us see what can be get from the second production in red. Production in red

From the production in Blue we have

Production in Blue

And the parsing can be stopped using $S\rightarrow \epsilon$

So from the above two work outs we find that the $a$'s and $b$'s are properly nested. (and can be mapped to the problem of valid parenthesization )

That being said let us work the options out:

Work out

Alternatively, during the examination, it is hard to get this detailed thought in mind, so one can try to draw the parse tree for any one of the words, trying to do so, you shall get the intuition of the semantics of the language of the grammar.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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