Teorema di Kleene

Questa voce o sezione sull'argomento matematica non cita le fonti necessarie o quelle presenti sono insufficienti.

---

Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti. Segui i suggerimenti del progetto di riferimento.

Questa voce sull'argomento matematica è solo un abbozzo.

Contribuisci a migliorarla secondo le convenzioni di Teknopedia. Segui i suggerimenti del progetto di riferimento.

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.

Si consideri un alfabeto finito ${\displaystyle A=\{a_{1},\ldots ,a_{n}\}}$. Un linguaggio ${\displaystyle 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 ${\displaystyle A}$ (o anche a partire dalle semplici lettere di ${\displaystyle A}$).

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.

Portale Matematica: accedi alle voci di Teknopedia che trattano di matematica