Language Recognizers accept
Recognizers are Machines
. The Machines take a string
if when run, the Machine stops
at an accept state
. Otherwise the input is rejected
. If a Machine M recognizes all strings
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 Grammar
s (CFGs) are a well known type of language generators.
Push Down Automata
s (PDAs) are a well known form of language recognizers.
s generate the same class of languages that are recognized by PDA