AngoLinux

Automi - Automa riconoscitore di stringa 11011

- A cura del Prof. Stefano Salvi -


Arriviamo finalmente agli automi riconoscitori.

Il testo dell'esercizio è il seguente:

Scrivere un automa riconoscitore in grado di riconoscere, in una sequenza continua di simboli scelti tra 1 e 0, ogni occorrenza della stringa 11011. La sequenza deve essere riconosciuta anche se è sovrapposta ad una precedente stringa riconosciuta (notare che il termine della sequenza potrebbe anche essere l'inizio di una nuova sequenza).
L'automa lavorerà sull'alfabeto { 0 , 1 }. L'unica uscita dell'automa assumertà il valore riconosciuto quando vine analizzato l'ultimo simbolo della stringa da riconoscere.

I ragazzi devono scrivere il seguente sorgente:
//automa che riconosce la seguente sequenza: 11011, riconosce anche le sequenze sovrapposte
autore{"Tizio"}

mealy
{
  alfabeto {"10"}
  
  stati {si,s1,s11,s110,s1101}
  
  output
  {
  	riconoscimento
  	{
  		{0,"non riconosciuto"},
  		{1,"riconosciuto"} 
  	}
  }
  		 
  transizione 
  {// 1      0   
    {s1,    si    },//si
    {s11,   si    },//s1    
    {s11,   s110  },//s11    
    {s1101, si    },//s110
    {s11,   si   } //s1101
  }  
  
  uscite 
  {//   1   0 
      {{0},{0}},//si
      {{0},{0}},//s1
      {{0},{0}},//s11
      {{0},{0}},//s110
      {{1},{0}} //s1101          
  }
}

L'automa risulterà come questo:

Per provare l'automa basta salvare il sorgente dell'automa in un file, copiandolo dalla pagina.


[Home Page dell'ITIS "Fermi"] [Indice Terza] [Precedente] [Successivo]

© Ing. Stefano Salvi - Released under GPL licence