Automa finito non deterministico

In NDFA, per un particolare simbolo di input, la macchina può spostarsi in qualsiasi combinazione degli stati nella macchina. In altre parole, non è possibile determinare lo stato esatto in cui si sposta la macchina. Quindi, si chiamaNon-deterministic Automaton. Poiché ha un numero finito di stati, la macchina viene chiamataNon-deterministic Finite Machine o Non-deterministic Finite Automaton.

Definizione formale di un NDFA

Un NDFA può essere rappresentato da una tupla di 5 (Q, ∑, δ, q ₀ , F) dove -

• Q è un insieme finito di stati.

• ∑ è un insieme finito di simboli chiamati alfabeti.

• δè la funzione di transizione dove δ: Q × ∑ → 2 ^Q

  (Qui è stato preso il power set di Q (2 ^Q ) perché in caso di NDFA, da uno stato, la transizione può avvenire a qualsiasi combinazione di stati Q)

• q₀è lo stato iniziale da cui viene elaborato qualsiasi input (q ₀ ∈ Q).

• F è un insieme di stati finali di Q (F ⊆ Q).

Rappresentazione grafica di un NDFA: (come DFA)

Un NDFA è rappresentato da digrafi chiamati diagramma di stato.

• I vertici rappresentano gli stati.
• Gli archi etichettati con un alfabeto di input mostrano le transizioni.
• Lo stato iniziale è indicato da un singolo arco in entrata vuoto.
• Lo stato finale è indicato da doppi cerchi.

Example

Sia un automa finito non deterministico →

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

La funzione di transizione δ come mostrato di seguito -

Stato attuale	Stato successivo per ingresso 0	Stato successivo per ingresso 1
un	a, b	b
b	c	corrente alternata
c	avanti Cristo	c

La sua rappresentazione grafica sarebbe la seguente:

DFA vs NDFA

La tabella seguente elenca le differenze tra DFA e NDFA.

DFA	NDFA
La transizione da uno stato è a un singolo particolare stato successivo per ogni simbolo di ingresso. Quindi è chiamato deterministico .	La transizione da uno stato può avvenire a più stati successivi per ogni simbolo di ingresso. Quindi è chiamato non deterministico .
Le transizioni di stringhe vuote non vengono visualizzate in DFA.	NDFA consente transizioni di stringhe vuote.
Il backtracking è consentito in DFA	In NDFA, il backtracking non è sempre possibile.
Richiede più spazio.	Richiede meno spazio.
Una stringa viene accettata da un DFA, se transita in uno stato finale.	Una stringa viene accettata da un NDFA, se almeno una di tutte le possibili transizioni termina in uno stato finale.

Accettori, classificatori e trasduttori

Accettatore (Riconoscitore)

Un automa che calcola una funzione booleana è chiamato un acceptor. Tutti gli stati di un accettore accettano o rifiutano gli input forniti.

Classificatore

UN classifier ha più di due stati finali e fornisce un singolo output quando termina.

Trasduttore

Un automa che produce output in base all'input corrente e / o allo stato precedente è chiamato a transducer. I trasduttori possono essere di due tipi:

• Mealy Machine - L'uscita dipende sia dallo stato corrente che dall'ingresso corrente.

• Moore Machine - L'uscita dipende solo dallo stato corrente.

Accettabilità da parte di DFA e NDFA

Una stringa viene accettata da un DFA / NDFA se e solo se il DFA / NDFA che inizia dallo stato iniziale termina in uno stato di accettazione (uno degli stati finali) dopo aver letto interamente la stringa.

Una stringa S è accettata da un DFA / NDFA (Q, ∑, δ, q ₀ , F), iff

δ*(q₀, S) ∈ F

La lingua L accettato da DFA / NDFA è

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

Una stringa S ′ non è accettata da un DFA / NDFA (Q, ∑, δ, q ₀ , F), iff

δ*(q₀, S′) ∉ F

La lingua L ′ non accettata da DFA / NDFA (Complemento della lingua accettata L) è

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

Example

Consideriamo il DFA mostrato nella Figura 1.3. Da DFA è possibile derivare le stringhe accettabili.

Stringhe accettate dal DFA precedente: {0, 00, 11, 010, 101, ...........}

Stringhe non accettate dal DFA precedente: {1, 011, 111, ........}