BrainTok
ENESIT

Linguaggi formali e automi: Automi a stati finiti e linguaggi regolari · Automi a stati finiti deterministici

Come funzionano gli automi a stati finiti deterministici, che cosa la loro memoria finita può e non può seguire e come progettarne di piccoli.

Linguaggi formali e automi · 28 domande

Prova 3 domande

1. Per ogni stato e simbolo di ingresso, quante transizioni definisce un automa a stati finiti deterministico (DFA)?

  1. Al massimo una
  2. Almeno una
  3. Esattamente una
Mostra la risposta

Risposta: Esattamente una

Essere deterministico significa che la funzione di transizione associa a ogni coppia (stato, simbolo) esattamente uno stato successivo, quindi il percorso della macchina su qualsiasi ingresso è completamente fissato.

2. Un DFA attraversa uno stato di accettazione a metà di una stringa, ma termina in uno stato non di accettazione. La stringa è accettata?

  1. Sì, basta raggiungere l'accettazione una volta
  2. No, conta solo lo stato finale
  3. Solo se la stringa non è vuota
Mostra la risposta

Risposta: No, conta solo lo stato finale

L'accettazione dipende soltanto dallo stato in cui si trova il DFA dopo aver letto l'ultimo simbolo; gli stati visitati lungo il percorso non contano.

3. Oltre a sapere in quale stato si trova, di quale memoria dispone un DFA?

  1. Un nastro di lettura e scrittura
  2. Nessuna
  3. Un unico contatore
Mostra la risposta

Risposta: Nessuna

L'unica memoria di un automa a stati finiti è quale dei suoi stati, in numero finito, sta occupando: proprio per questo non può contare senza limiti.

Il resto del quiz, poche domande alla volta

BrainTok ti fa qualche domanda da quiz come questi prima di aprire le app che scegli, e il tempo davanti allo schermo diventa apprendimento. Per iPhone.

Unisciti alla beta

Altri quiz di Informatica