Search code examples
formal-languages

Language generated by a Context Free Grammar?


enter image description here

What is the language generated by this language? i would say its all words with exactly 2 or 3 b's but i'm not quite sure.


Solution

  • Any number of 'a's before, after and between either 2 or 3 'b's.

    It is progressive... any number of S, followed by any number of X, followed by any number of Y, with, optionally, any number of Z. Each of these elements can be any number of the character 'a'. S, X, and Y all move on to the next element when a 'b' is encountered. Y can terminate before a 'b' is seen (thus, a 'b' from S and a 'b' from X are guaranteed, but not one from Y).