Ask your own question, for FREE!
Computer Science 16 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!
Latest Questions
Arriyanalol: i need help
2 days ago 7 Replies 1 Medal
Arriyanalol: CONGRATS to me
2 days ago 8 Replies 2 Medals
Legomaster346: What colleges are good that are near Arab Alabama?
1 week ago 5 Replies 0 Medals
Arriyanalol: i need help
1 week ago 6 Replies 2 Medals
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!