Terza Prova - Informatica e Sistemi

  • Materia: Terza Prova - Informatica e Sistemi
  • Visto: 1237
  • Data: 22/04/2012
  • Di: Redazione StudentVille.it

Controllabilità, raggiungibilità e indistinguibilità degli automi

Relativamente agli automi si dia il significa di controllabilità, raggiungibilità e indistinguibilità

Con la controllabilità si studia la possibilità di trasferire lo stato di un sistema ad uno stato prefissato chiamato stato zero; cioè la possibilità, di controllare i vari stati di un sistema, mediante opportuni ingressi, ad uno stato finale desiderato è detto controllabilità.

Con la raggiungibilità si cerca partendo dallo stato zero, di imporre al sistema il raggiungimento di un qualsiasi stato, cioè è importante ai fini dell’automazione stabilire se è possibile, attraverso una opportuna sequenza di ingresso,raggiungere i vari stati di un sistema a partire da un dato stato iniziale. Questo problema è noto come raggiungibilità.

Per i sistemi queste due proprietà non dipendono l’una dall’altra.

Parleremo di indistinguibilità quando non è possibile distinguere con esperimenti il comportamento dell’automa. Ovviamente due stati sono indistinguibili se e solo se non sono distinguibili. Quindi possiamo concludere che due stati dell'automa sono indistinguibili se, per ogni parola presentata, l'automa va in uno stato finale oppure non ci va indipendentemente dallo stato di partenza.