# Automi FSA

## Automi a stati finiti (asf, fsa)

Costituiti da:
- Insieme finito di stati ($Q$)
- Un insieme finito (alfabeto) di ingressi ($I$)
- Una funzione di transizione (parziale): $\delta: Q$ x $I \to Q$
- Uno stato iniziale $q_0 \in Q$
- Uno o più stati finali $F \in Q$
- Il tutto rappresentato nella forma <$Q, I, \delta, q_0, F$>

Riconosce un linguaggio $L$ se partendo da uno stato iniziale ($q_0 \in Q$), facendo una sequenza di mosse ($\delta$*), arriva in uno stato finale (o di accettazione, $F\subseteq Q$):
- $x \in L \iff \delta$*$(q_0,x) \in F$

Sequenza di mosse:
- $\delta$*: $Q$ x $I$\* $\to Q$ dove $\delta$\* è definita ricorsivamente a partire da $\delta$:
- $\delta$*$(q,\varepsilon) = q$
- $\delta$*$(q,y.i) = \delta(\delta$\*$(q,y), i)$

## Automi traduttori
Sono automi a stati finiti a cui viene aggiunto un alfabeto output $O$ ed una funzione $\eta: Q$ x $I$\* $\to O$\*
e bla bla bla

## Pumping lemma
Premessa: $\exists x \in L$, L riconosciuto da un FSA, $|x| > |Q|$
Conseguenza: esistono $q \in Q, w \in I^+$ tali che $x = ywz$ con $y,z \in I^*$ e $\delta^*(q, w)=q$
Inoltre $\forall n\geq0$, $yw^nz \in L$
- ovvero esiste una sottostringa di $x$ che viene riconosciuta dall'automa effettuando un'iterazione su un ciclo di stati

Conseguenze del pumping lemma:
- $L = \varnothing$ se:
- $\exists x \in L \iff \exists y \in L,\ |y|<|Q|$ , ovvero mi basta controllare tutte e sole le stringhe di lunghezza minore della cardinalità di Q
- $L = \infty$ se:
- $\exists x \in L,\ |Q|\leq|x|<2|Q|$, ovvero mi basta controllare tutte e sole le stringhe di lunghezza compresa tra |Q| e 2|Q|
- Non potrò mai accettare linguaggi del tipo $L=\{a^nb^n|n>0\}$ perché non potrò mai "pompare" una sua parte. In generale non potrò mai accettare un linguaggio dove è necessario "contare" un numero n non definito a priori.

## Linguaggi riconosciuti

Vengono riconosciuti dagli FSA:
- tutti i linguaggi finiti
- tutti i linguaggi riconosciuti dagli FSAND (equivalenza tra FSA e FSAND)
- tutti i linguaggi prodotti da grammatiche regolari

I linguaggi riconosciuti dagli FSA vengono detti *linguaggi regolari*, o *regular expressions*, o *REG*
Le REG sono chiuse rispetto a tutti gli operatori insiemistici:
- unione creando un ASFND con i due ASF
- intersezione creando $<A1, A2>\ =\ <Q_1$ x $Q_2, I, \delta, <q_0^1, q_0^2 >, F1$ x $F2 >$
- negazione invertendo stati finali e non finali -funziona solo se funzione di transizione è totale

## FSAND
Sono equivalenti agli FSA, e quindi equipotenti. A partire da un FSAND se ne costruisce uno deterministico in questo modo:
- ogni volta che c'è un passaggio non deterministico da $q_0$ a $q_1$ e $q_2$: si crea un nuovo stato ({$q_1, q_2$}), da cui partiranno tutte le frecce che uscvano da $q_1$ e da $q_2$
- tutti gli stati creati che contengono almeno uno stato di accettazione (del FSAND) divengono stati di accettazione

## To add:
- esempi