Saltar para o conteúdo

Reconhecedores

Origem: Wikipédia, a enciclopédia livre.
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

[editar | editar código-fonte]

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

Estados de aceitação

[editar | editar código-fonte]
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 é 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.

S1 (que também é o estado inicial) indica o estado em que um número par de 0s foi dado como entrada. S1 é, 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
Este artigo é um esboço. Você pode ajudar a Wikipédia expandindo-o. Editor: considere marcar com um esboço mais específico.
Teoria de autômatos: linguagem formal e gramática formal
Hierarquia
Chomsky
Gramática Linguagem Reconhecedor
Tipo-0 Irrestrita Recursivamente enumerável Máquina de Turing
-- -- Recursiva Máquina de Turing que sempre para
Tipo-1 Sensível ao contexto Sensível ao contexto Autômato linearmente limitado
Tipo-2 Livre de contexto Livre de contexto Autômato com pilha
Tipo-3 Regular Regular Autômato finito