Na•ve Solution to the
Recognition Problem
lTo determine whether string x is in the language generated by a grammar:
lStart with the start symbol.
lGenerate strings successively by applying productions.
lEventually either:
lThe string x is generated, or
lThe new strings being generated all exceed x in length.
lSo we can tell whether or not x is ever generated.