display | more...
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.

Log in or register to write something here or to contact authors.