Reconhecedores – Wikipédia, a enciclopédia livre

Este artigo não cita fontes confiáveis. Ajude a inserir referências. Conteúdo não verificável pode ser removido.—Encontre fontes: ABW  • CAPES  • Google (N • L • A) (Junho de 2021)

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.

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

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

• Linguagem recursivamente enumerável

Este artigo é um esboço. Você pode ajudar a Wikipédia expandindo-o.

Editor: considere marcar com um esboço mais específico.