Teorema di Kleene

Il teorema di caratterizzazione degli automi finiti di Kleene afferma che i linguaggi regolari, cioè i linguaggi accettati da un riconoscitore di Rabin e Scott (RSR), sono tutti e soli i linguaggi a stati finiti ottenuti con un'operazione di chiusura. Il teorema è dovuto a Stephen Kleene.

Enunciato

Si consideri un alfabeto finito $A=\{a_{1},\ldots ,a_{n}\}$. Un linguaggio $L$ su tale alfabeto è regolare se e solo se si può individuare con un'espressione regolare, ossia se si può ottenere applicando le operazioni di unione (∪), giustapposizione (⋅) e star chiusura (*) a linguaggi finiti su $A$ (o anche a partire dalle semplici lettere di $A$).

Idea della dimostrazione

Si effettua in due parti, come molte dimostrazioni di proprietà di equivalenza di strumenti (in questo caso i riconoscitori di Rabin e Scott e le espressioni regolari). In una prima parte si dimostra che ogni linguaggio accettato da un RSR soddisfa certe equazioni sui linguaggi che possono essere risolte univocamente portando ad espressioni regolari. In una seconda a partire da un'espressione regolare si individua un RSR che accetta il linguaggio che l'espressione individua.