Ask your own question, for FREE!
Computer Science 15 Online
OpenStudy (anonymous):

Any string of terminals that can be generated by the following CFG- S -> XY X -> aX | bX | a Y -> Ya | Yb | a

OpenStudy (anonymous):

So your grammar is the following: S -> XY X -> aX | bX | a Y -> Ya | Yb | a To provide a string that is according to this grammar, you'll need to ask yourself what kind of strings will match the criteria of the grammar. Since S is 'just' an X followed by an Y, you can create strings for X and Y and then concatenate them. So when is a string a valid X? Is e.g. "baab" a valid X? and what about "baba"? and "aba"?

OpenStudy (anonymous):

Ah, finite grammars, I remember you well. I usually find it worthwhile to ask "what is the shortest possible string?" in cases like these where, at first glance, it looks like the string could be almost anything. Really, the only stipulations of this string is that it has to contain a's and b's and it has to include a small string somewhere within it.

Can't find your answer? Make a FREE account and ask your own questions, OR help others and earn volunteer hours!

Join our real-time social learning platform and learn together with your friends!
Can't find your answer? Make a FREE account and ask your own questions, OR help others and earn volunteer hours!

Join our real-time social learning platform and learn together with your friends!