Search code examples
context-free-grammarcontext-free-language

description of the language accepted by S->SS|bS|a

I want to know what language is generated by this CFG

S → SS | bS | a

I have obtained some strings but cannot find a pattern

abbaaaa
aaaaaaa
ba
aaaaa
aaaaaaabaaaabbaa
babaaabaaaba
bbbababaababaa
baabaa
baa
aaaaaabbaaabbba
Solution
    • This grammar does not generate epsilon;
    • The minimum length string generated by S is "a". Also last character generated by S is also a;
    • bS means that if there is b in the string then after it there must be more characters (because the grammar does not generate epsilon). These characters could be more b, but eventually a must follow (as noted up). That is n times of b, where n >= 0;
    • Because of SS the language allows repetitions (an infinite number of times (k)) of this zero or more b characters followed by one a.

    The language L should be this (where Sigma is the alphabet):

    language L

    This could be written with regular expression like this:

    regex