Recognizer

from Wikipedia, the free encyclopedia

A Recognizer ( Engl. To recognize "recognize"), even recognizer is in computer science a particular abstract machine model, a so-called machine . This automaton determines on the basis of a formal grammar whether a specific word is an element of a formal language or not. The language is defined or generated by the underlying formal grammar. The Recognizer only decides whether an input text is “correct” or “incorrect” with regard to the specifications; this distinguishes it from a parser , which can also describe and output the analyzed grammatical structure. A typical example of a recognizer in automaton theory is the push-down automaton .

Example of a recognizer

In the Prolog programming language , so-called Definite Clause Grammars (DCG) can be used to create and process some context-free grammars . Applied to machine language processing , the following example of a DCG shows a very simple grammar with which a small number of German sentences can be analyzed. The grammar rules specify that a set of a nominal - (NP) and a verb phrase composed, the NP in turn consists of an article and a noun , both in number and gender must match. In the lexicon, the lexical units are defined as terminal symbols. The Prolog query recognize ('list of words') starts the recognizer , which decides whether a sequence of words is grammatical based on the modeled DCG or not.

 % Grammatikregeln:
 satz          --> nominalphrase, verbalphrase.
 nominalphrase --> artikel(Numerus, Genus), nomen(Numerus, Genus).
 verbalphrase  --> finites_verb.

 % Lexikon:
 artikel(singular, maskulin) --> [der].
 artikel(singular, feminin)  --> [die].
 nomen(singular, maskulin)   --> [hund].
 nomen(singular, feminin)    --> [katze].
 finites_verb                --> [bellt].

 recognize(Satz) :- satz(Satz, []).

The request to the Recognizer is successful (the example sentence is grammatical):

 ?- recognize([der, hund, bellt]).
 Yes

The request to the Recognizer is unsuccessful (the example sentence is ungrammatic):

 ?- recognize([der, katze, bellt]).
 No

Web links