Automi

Argomenti

• Teoria degli automi
  • Il primo passo per capire modelli semplici di computazione
• Computabilità
  • Modello da calcolo molto più potente (macchina di Turing)
• Complessità
  • Quantificare le risorse in termini di spazio e tempo

Linguaggi regolari

Alfabeto

Definiamo come alfabeto un insieme finito di elementi detto simboli

L’insieme $\Sigma =\{0,1,x,y,z\}$ è un alfabeto

Stringa o Parola

Data una sequenza di simboli $w_1,\dots ,w_n\in \Sigma$, definiamo:

$$w:=w_1,\dots ,w_n$$

come stringa (o parola) di $\Sigma$

Dato l’alfabeto $\Sigma =\{0,1,x,y,z\}$, una stringa di $\Sigma$ è $0x1yyy0$

Linguaggio

Dato un alfabeto $\Sigma$, definiamo come linguaggio di $\Sigma$, indicato con ${\Sigma }^{\ast }$, l’insieme delle stringhe di $\Sigma$

Lunghezza di una stringa

Data una stringa $w\in {\Sigma }^x$, definiamo la lunghezza di $w$, indicata come $|w|$, come il numero di simboli presenti in $w$

Concatenazione

Data la stringa $x:=x_1,\dots ,x_n\in {\Sigma }^x$ e la stringa $y_1,\dots ,y_n\in \Sigma$, definiamo come concatenazione di $x$ in $y$ la seguente operazione:

$$xy=x_1\dots x_n{y}_1\dots y_n$$

Conteggio

Data una stringa $w\in {\Sigma }^{\ast }$ e un simbolo $a\in \Sigma$ definiamo il conteggio di $a$ in $w$, indicato come $|w{|}_a$, il numero di simboli uguali ad $a$ presenti in $w$

Data la stringa $w:=010101000\in \{0,1{\}}^{\ast }$, si ha che $|w{|}_0=6$ e $|w{|}_1=3$

Automi a stati finiti DFA Ha una quantità di memoria limitata e processa in modo semplice i dati. Processa input bit a bit in modo sequenziale.

Esempio …

Astraendo, un DFA sarà fatto nel seguente modo:

• $q_1,q_2,q_3$ sono stati
• $q_2$ è lo stato di accettazione
• Gli archi sono le transizioni

Definizione DFA

Un DFA è una tupla:

$$(Q,\sum ,\delta ,q_0,F)$$

Dove:

• Q è un numero finito degli stati
• Sigma è un numero finito dei simboli

Teorema dell'unione