Reconhecedores
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a8/Fsm_parsing_word_nice.svg/400px-Fsm_parsing_word_nice.svg.png)
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
![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/9d/DFAexample.svg/220px-DFAexample.svg.png)
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 |
Ver também
![]() | 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 |