Automa a stati finiti

[fatina biondina]

Automa a stati finiti

Da Wikipedia, l'enciclopedia libera.

Un automa a stati finiti è un sistema dinamico, invariante, discreto nell'avanzamento e nelle interazioni nel quale gli insiemi dei possibili valori di ingresso, uscita e stato sono insiemi finiti.

• dinamico: evolve nel tempo passando da uno stato all'altro in funzione dei segnali d'ingresso e dello stato precedente;
• invariante: a paritÃ* di condizioni iniziali il comportamento del sistema è sempre lo stesso;
• discreto: le variabili d'ingresso, di stato, d'uscita, possono assumere solo valori discreti.

L' automa a stati finiti è un modello di calcolo semplice rappresentabile come un piccolo dispositivo, che mediante una testina legge una stringa di input su un nastro e la elabora, facendo uso di un meccanismo molto semplice di calcolo e di una memoria limitata. L'esame della stringa avviene un carattere alla volta attraverso precisi passi computazionali che comportano l'avanzamento della testina. In sostanza un ASF è un caso particolare di macchina di Turing, utilizzato per l'elaborazione di quei linguaggi che nelle Grammatiche di Chomsky sono definiti di Tipo 3 o Regolari. Distinguiamo due tipi di automi a stati finiti: gli automi a stati finiti deterministici (ASFD) e gli automi a stati finiti non deterministici ASFND.
Indice

• [Solo gli utenti registrati possono visualizzare tutti i links]
  
  • 1.1 Automa a stati finiti deterministico
  • 1.2 Automa a stati finiti non deterministico
  • 1.3 Differenza tra ASFD ed ASFND
• 2 Automa di Mealy e Automa di Moore

Definizione formale


Automa a stati finiti deterministico

Un automa a stati finiti deterministico si definisce come un sistema A = {I, U, S, f, g}, dove

• I = {i1, i2, ... in} è l'insieme finito dei possibili simboli in ingresso
• U = {u1, u2, ..., um} insieme finito dei possibili simboli in uscita
• S = {s1, s2, ..., sh} insieme finito degli stati
• f = I × S → U funzione delle uscite (eventualmente parziale), che collega l'uscita al valore attuale dell'ingresso e dello stato, U(t)=f (S(t), I(t))
• g = I ×S → S funzione di transizione degli stati interni successivi, che collega lo stato nell'istante successivo al valore attuale dell'ingresso e dello stato, S(t+1)=g(S(t), I(t))

Automa a stati finiti non deterministico

Un automa a stati finiti non deterministico si definisce come un sistema A = {I, U, S, f, g}, dove

• I = {i1, i2, ... in} è l'insieme finito dei possibili simboli in ingresso
• U = {u1, u2, ..., um} insieme finito dei possibili simboli in uscita
• S = {s1, s2, ..., sh} insieme finito degli stati
• f = I × S → U funzione delle uscite (eventualmente parziale), che collega l'uscita al valore attuale dell'ingresso e dello stato, U(t)=f (S(t), I(t))
• g = I ×S → P(S) funzione di transizione parziale degli stati interni successivi, che collega al valore attuale dell'ingresso e dello stato un sottoinsieme di S.

Differenza tra ASFD ed ASFND

Sostanzialmente la differenza tra i due tipi di automi (giÃ* espressa dalle definizioni formali) consiste nel fatto che nei primi, in qualunque stato ci si trovi, per un qualsivoglia input, esisterÃ* una ed una sola transizione, mentre nei secondi, almeno uno stato presenta più di una possibile computazione per determinati caratteri in ingresso. Da notare che il determinismo è un caso particolare di non determinismo, tuttavia, nel caso degli automi a stati finiti, è possibile passare agevolmente dall'uno all'altro. L'idea è quella di unire in un unico stato collettivo [s1,s2,...,sk] gli stati s1,s2,...,sk raggiungibili con lo stesso ingresso, ovvero quelli che causano l'indeterminatezza dell'automa.

Automa di Mealy e Automa di Moore

Nell'automa di Moore, la funzione f dipende solo dallo stato: f = S → U e dunque U(t)=f (S(t)). La macchina di Moore può essere dunque vista come una semplificazione del caso più generico, dove l'uscita dipende dallo stato e dagli ingressi. Quest'ultimo tipo di automa è detto automa di Mealy.


Teoria degli automi: linguaggi formali e grammatiche formali

• Tipo-0 [gerarchia di Chomsky]
  1. (illimitato) [Grammatiche]
  2. Ricorsivamente enumerabile [Linguaggi]
  3. Macchina di Turing [automa minimo]

• 1. (illimitato) [Grammatiche]
  2. Ricorsivo [Linguaggi]
  3. Decider[automa minimo]
• Tipo-1 [gerarchia di Chomsky]
  • Sensibile al contesto [Grammatiche]
  • Sensibile al contesto [Linguaggi]
  • Lineare-limitato[automa minimo]
• Tipo-2 [gerarchia di Chomsky]
  • Libero dal contesto [Grammatiche]
  • Libero dal contesto [Linguaggi]
  • Automa a pila[automa minimo]
• Tipo-3 [gerarchia di Chomsky]
  • Lineare (o Regolare) [Grammatiche]
  • Lineare (o Regolare) [Linguaggi]
  • A stati finiti [automa minimo]

Ciascuna categoria di linguaggio o grammatica è un sottoinsieme del proprio sovrainsieme di categoria direttamente sottostante.

[Solo gli utenti registrati possono visualizzare tutti i links]


(questo argomento mi sta antipatico ma molto.. )

[danilotrix]

mi aiutate a fare quest esercizio?

1. Costruire l’automa a stati finiti non deterministico con E-transizioni che accetta il linguaggio formato da tutte le stringhe sull’alfabeto {a,b} che contengono almeno due occorrenze della stringa “ab” oppure contengono un numero pari di “b”. ( aaabb, ababba, ababa E L mentre aaba, baabb non appartengono a L)