Language Recognizers accept a Language.
Recognizers are
Machines. The Machines take a
string as input.
The
Machines will
accept the
input if when run, the Machine stops
at an
accept state. Otherwise the input is
rejected. If a Machine M recognizes all
strings in
Language L, and
accepts input provided by a given string S, M is said to accept S. Otherwise M is said to reject S.
S is in L
if and only if M accepts S.
Language Generators create the strings of a Language.
Generators are string
constructors. A generator provides a
construction description. If a
generator is able to
construct all stings in a Language L, and every string S that can be constructed by that generator is in L, we can say that the generator is a generator for the language L. If there is no way to construct a string S from the generator, S
is not in L.
Context Free Grammars (CFGs) are a well known type of language generators.
Push Down Automatas (PDAs) are a well known form of language recognizers.
CFGs generate the same class of languages that are recognized by
PDAs.