Autômato Finito Não Determinístico

No NDFA, para um símbolo de entrada específico, a máquina pode se mover para qualquer combinação dos estados na máquina. Em outras palavras, o estado exato para o qual a máquina se move não pode ser determinado. Por isso, é chamadoNon-deterministic Automaton. Por possuir número finito de estados, a máquina é chamadaNon-deterministic Finite Machine ou Non-deterministic Finite Automaton.

Definição formal de um NDFA

Um NDFA pode ser representado por uma 5-tupla (Q, ∑, δ, q ₀ , F) onde -

• Q é um conjunto finito de estados.

• ∑ é um conjunto finito de símbolos chamados alfabetos.

• δé a função de transição onde δ: Q × ∑ → 2 ^Q

  (Aqui, o conjunto de potência de Q (2 ^Q ) foi tomado porque no caso de NDFA, de um estado, a transição pode ocorrer para qualquer combinação de estados Q)

• q₀é o estado inicial de onde qualquer entrada é processada (q ₀ ∈ Q).

• F é um conjunto de estados / estados finais de Q (F ⊆ Q).

Representação gráfica de um NDFA: (igual ao DFA)

Um NDFA é representado por dígrafos chamados de diagrama de estado.

• Os vértices representam os estados.
• Os arcos marcados com um alfabeto de entrada mostram as transições.
• O estado inicial é denotado por um único arco de entrada vazio.
• O estado final é indicado por círculos duplos.

Example

Seja um autômato finito não determinístico →

• Q = {a, b, c}
• ∑ = {0, 1}
• q ₀ = {a}
• F = {c}

A função de transição δ conforme mostrado abaixo -

Estado atual	Próximo estado para a entrada 0	Próximo estado para a entrada 1
uma	a, b	b
b	c	a, c
c	b, c	c

Sua representação gráfica seria a seguinte -

DFA vs NDFA

A tabela a seguir lista as diferenças entre DFA e NDFA.

DFA	NDFA
A transição de um estado é para um único próximo estado particular para cada símbolo de entrada. Por isso é chamado de determinístico .	A transição de um estado pode ser para vários próximos estados para cada símbolo de entrada. Por isso é chamado de não determinístico .
Transições de string vazias não são vistas no DFA.	NDFA permite transições de string vazias.
Retrocesso é permitido no DFA	No NDFA, o retrocesso nem sempre é possível.
Requer mais espaço.	Requer menos espaço.
Uma string é aceita por um DFA, se transita para um estado final.	Uma string é aceita por um NDFA, se pelo menos uma de todas as transições possíveis terminar em um estado final.

Aceitadores, classificadores e transdutores

Aceitador (Reconhecedor)

Um autômato que calcula uma função booleana é chamado de acceptor. Todos os estados de um aceitador estão aceitando ou rejeitando as entradas fornecidas a ele.

Classificador

UMA classifier tem mais de dois estados finais e fornece uma única saída quando termina.

Transdutor

Um autômato que produz saídas com base na entrada atual e / ou estado anterior é chamado de transducer. Os transdutores podem ser de dois tipos -

• Mealy Machine - A saída depende do estado atual e da entrada atual.

• Moore Machine - A saída depende apenas do estado atual.

Aceitabilidade por DFA e NDFA

Uma string é aceita por um DFA / NDFA iff o DFA / NDFA começando no estado inicial termina em um estado de aceitação (qualquer um dos estados finais) depois de ler a string completamente.

Uma string S é aceita por um DFA / NDFA (Q, ∑, δ, q ₀ , F), iff

δ*(q₀, S) ∈ F

O idioma L aceito pelo DFA / NDFA é

{S | S ∈ ∑* and δ*(q₀, S) ∈ F}

Uma string S ′ não é aceita por um DFA / NDFA (Q, ∑, δ, q ₀ , F), iff

δ*(q₀, S′) ∉ F

O idioma L ′ não aceito pelo DFA / NDFA (Complemento do idioma L aceito) é

{S | S ∈ ∑* and δ*(q₀, S) ∉ F}

Example

Vamos considerar o DFA mostrado na Figura 1.3. A partir do DFA, as strings aceitáveis ​​podem ser derivadas.

Strings aceitas pelo DFA acima: {0, 00, 11, 010, 101, ...........}

Strings não aceitos pelo DFA acima: {1, 011, 111, ........}