For faster navigation, this Iframe is preloading the Wikiwand page for Automa a stati finiti non deterministico.

Automa a stati finiti non deterministico

Da Wikipedia, l'enciclopedia libera.

Esempio di ASFND

Nella teoria del calcolo, un automa a stati finiti non deterministico (ASFND, in inglese nondeterministic finite automaton, NFA) è una macchina a stati finiti dove per ogni coppia stato-simbolo in input possono esservi più stati di destinazione.

Al contrario degli automi a stati finiti deterministici, gli NFA possono cambiare stato indipendentemente dal simbolo letto, tramite epsilon-transizioni. Gli automi che presentano questo tipo di transizioni sono anche detti ε-NFA.

Definizione formale

[modifica | modifica wikitesto]

Un automa a stati finiti non deterministico è una quintupla con:

  • insieme finito di simboli chiamato alfabeto
  • insieme finito di stati
  • funzione di transizione, dove è l'insieme delle parti di S
  • stato iniziale
  • insieme di stati finali

Dato un NFA ed una stringa , A accetta la stringa con se esiste una sequenza di stati tale che:

La macchina parte dallo stato iniziale e legge una stringa. Attraverso la relazione di transizione si determina lo stato o gli stati di destinazione in base allo stato corrente ed al simbolo letto. Se dopo aver letto l'ultimo simbolo la macchina si trova in almeno uno degli stati appartenenti ad F, la macchina accetta la stringa, altrimenti la rifiuta. L'insieme di tutte le stringhe accettate dall'automa a stati finiti non deterministico è il linguaggio accettato dall'automa.

Il linguaggio accettato dagli automi a stati finiti non deterministico è un linguaggio regolare.

Equivalenza tra automa non deterministico e deterministico

[modifica | modifica wikitesto]

Per ogni automa a stati finiti non deterministico è possibile costruire un automa a stati finiti deterministico in grado di riconoscere lo stesso linguaggio utilizzando la costruzione dei sottoinsiemi.

Automa a stati finiti non deterministico con epsilon-transizioni

[modifica | modifica wikitesto]

È possibile definire una variante degli automi a stati finiti non deterministici che permetta transizioni di stato spontanee, ossia transizioni su stringa vuota . Per tali automi è sufficiente ridefinire la funzione di transizione come:

.

Funzione di chiusura su

[modifica | modifica wikitesto]

La funzione di chiusura su si definisce induttivamente.
Base: .
Ipotesi induttiva: .
Passo induttivo: .

Funzione di transizione estesa

[modifica | modifica wikitesto]

La funzione di transizione estesa va ridefinita in termini di come segue:
Base: .
Ipotesi induttiva: .
Passo induttivo: .

Il seguente esempio mostra un automa a stati finiti non deterministico , sull'alfabeto binario, in grado di determinare se la stringa in input contiene un numero pari di zero o di uno.

dove

  • La funzione di transizione è definita dalla seguente tabella di transizione:
0 1
Automa a stati finiti dell'esempio

È inoltre importante far notare che può essere ricavato dall'unione di due automi a stati finiti deterministici i cui stati sono rispettivamente e . Il linguaggio regolare riconosciuto dall'automa è inoltre esprimibile tramite l'espressione regolare

  • (EN) nondeterministic finite automaton, in Academic Press Dictionary of Science and Technology, Oxford, Elsevier Science & Technology, 1992.
  • (EN) automata theory, in Encyclopedia of Computer Science, Hoboken, Wiley, 2003.
  • (EN) John E. Hopcroft, Rajeev Motwani; Jeffrey D. Ullman, Finite Automata, in Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 15 luglio 2006, ISBN 978-0-321-46225-1.
  • (EN) Martin Davis, Ron Sigal; Elaine J. Weyuker, Finite Automata, in Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science, Morgan Kaufmann, 17 febbraio 1994, ISBN 978-0-12-206382-4.

Voci correlate

[modifica | modifica wikitesto]

Altri progetti

[modifica | modifica wikitesto]
  Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica
{{bottomLinkPreText}} {{bottomLinkText}}
Automa a stati finiti non deterministico
Listen to this article

This browser is not supported by Wikiwand :(
Wikiwand requires a browser with modern capabilities in order to provide you with the best reading experience.
Please download and use one of the following browsers:

This article was just edited, click to reload
This article has been deleted on Wikipedia (Why?)

Back to homepage

Please click Add in the dialog above
Please click Allow in the top-left corner,
then click Install Now in the dialog
Please click Open in the download dialog,
then click Install
Please click the "Downloads" icon in the Safari toolbar, open the first download in the list,
then click Install
{{::$root.activation.text}}

Install Wikiwand

Install on Chrome Install on Firefox
Don't forget to rate us

Tell your friends about Wikiwand!

Gmail Facebook Twitter Link

Enjoying Wikiwand?

Tell your friends and spread the love:
Share on Gmail Share on Facebook Share on Twitter Share on Buffer

Our magic isn't perfect

You can help our automatic cover photo selection by reporting an unsuitable photo.

This photo is visually disturbing This photo is not a good choice

Thank you for helping!


Your input will affect cover photo selection, along with input from other users.

X

Get ready for Wikiwand 2.0 🎉! the new version arrives on September 1st! Don't want to wait?