Teorema di Kleene

Espressioni regolari e automi finiti sono equivalenti nella loro potenza descrittiva

Ogni espressione regolare può essere convertita in un automa finito che riconosce il linguaggio che essa descrive e viceversa

Data una espressione regolare $R$ indichiamo con $L(R)$ il linguaggio descritto da $R$

<aside> 💡 Un linguaggio è regolare se e solo se esiste una espressione regolare che lo descrive

</aside>

• Idea

Lemma

<aside> 💡 Se un linguaggio è descritto da un’espressione regolare, allora esso è regolare

</aside>

• Dimostrazione

Lemma

<aside> 💡 Se un linguaggio è regolare, allora è descritto da un’espressione regolare

</aside>

• Dimostrazione