AngoLinux

Automi - Automa riconoscitore di stringhe abbc e bca

- A cura del Prof. Stefano Salvi -


E, per finire, un secondo automa riconoscitore.

Il testo dell'esercizio è il seguente:

Scrivere un automa riconoscitore in grado di riconoscere, in una sequenza continua di simboli scelti tra a, b e c, ogni occorrenza di una o dell'altra delle stringhe abbc o bca. Le sequenza deve essere riconosciute anche se sono sovrapposte una all'altra (notare che il termine di una sequenza potrebbe anche essere l'inizio dell'altra).
L'automa lavorerà sull'alfabeto { a , b , c }. L'unica uscita dell'automa assumertà il valore riconosciuto ABBC quando vine analizzato l'ultimo simbolo della stringa abbc e riconosciuto BCA quando vine analizzato l'ultimo simbolo della stringa bca.

I ragazzi devono scrivere il seguente sorgente:
//automa che riconosce le seguenti sequenze: abbc e bca, riconosce anche le sequenze sovrapposte
autore{"Tizio"}

mealy
{
  alfabeto {"abc"}
  
  stati {si,sa,sb,sab,sbc,sabb}
  
  output
  {
  	riconoscimento
  	{
  				{0,"non riconosciuto"},
  				{1,"riconosciuto ABBC"},
  				{2,"riconosciuto BCA"} 
  	}
  }
  		 
  transizione 
  {// a    b     c   
    {sa,   sb,   si  },//si
    {sa,   sab,  si  },//sa    
    {sa,   sb,   sbc },//sb    
    {sa,   sabb, sbc },//sab
    {sa,   sb,   si  },//sbc
    {sa,   sb,   sbc } //sabb
  }  
  
  uscite 
  {//   a   b   c
      {{0},{0},{0}},//si
      {{0},{0},{0}},//sa
      {{0},{0},{0}},//sb
      {{0},{0},{0}},//sab
      {{2},{0},{0}},//sbc
      {{0},{0},{1}} //sabb         
  }
}

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