Reconhecedores

Fig. 1 Reconhecedor: analisando a palavra "nice"

Reconhecedores produzem uma saída binária, tendo como resposta ou sim ou não caso a entrada seja aceita pela máquina ou não. No momento em que toda a entrada é processada, se o estado atual for de aceitação, a entrada é aceita, se não, é rejeitada. O exemplo na figura 1 mostra uma FSM (Máquina de Estados Finita) que aceita a palavra 'nice'. Nessa MSF, o único estado de aceitação é o número 7.

A máquina pode também ser descrita como se define uma linguagem, que deve conter todas as palavras aceitas por ela e nenhuma rejeitada; dizemos que a linguagem é aceita pela máquina. Por definição, as linguagens aceitas pelas FSMs são as linguagens regulares- isto é, uma linguagem é regular se alguma FSM aceita ela.

Estado Inicial

O estado inicial geralmente é mostrado com uma seta desenhada apontando para ele.

Estados de aceitação

Fig. 5: Representação de uma Máquina de Estados Finita; esse exemplo mostra uma que determina se uma cadeia binária tem um número par ou ímpar de 0's, onde $S_{1}$ é um estado de aceitação.

Estados de aceitação são aqueles no qual a máquina afirma que a entrada, já processada por completo, é membro da linguagem que ela aceita. Geralmente é representada por dois círculos.

Um exemplo de um estado de aceitação aparece no diagrama ao lado: um DFA Autômato finito determinístico que detecta se uma entrada composta somente por 1s e 0s contém um número par de 0s.

S₁ (que também é o estado inicial) indica o estado em que um número par de 0s foi dado como entrada. S₁ é, portanto, um estado de aceitação. Essa máquina irá terminar em um estado de aceitação se a entrada contiver um número par de 0s (incluindo cadeias que não contém nenhum 0). Exemplos de cadeias aceitas por essa DFA são epsilon (a cadeia vazia), 1, 11, 11..., 00, 010, 1010, 10110, etc...

Tabela de correspondência
Gramáticas	Reconhecedores
Com estrutura de Frase ou Tipo 0	Máquina de Turing
Sensíveis ao Contexto ou Tipo 1	Máquina de Turing com memória limitada
Livres de Contexto ou Tipo 2	Autômatos a Pilha
Regulares ou Tipo 3	Autômatos Finitos

Ver também

• Linguagem recursivamente enumerável