Teorema lui Kleene
Teorema lui Kleene pentru caracterizarea automatelor finite afirmă că limbajele obișnuite, adică limbile acceptate de un recunoscător Rabin și Scott (RSR), sunt toate și numai limbaje cu stări finite obținute cu o operație de închidere. Teorema se datorează lui Stephen Kleene .
Teză
Luați în considerare un alfabet finit . O limbă L pe acest alfabet este regulată dacă și numai dacă poate fi identificată cu o expresie regulată, adică dacă poate fi obținută prin aplicarea operațiilor de unire (∪), juxtapunere (⋅) și închidere stea (*) la limbi finite pe A (sau chiar pornind de la literele simple ale lui A ).
Sugestie pentru demonstrație
Se face în două părți, la fel ca multe dovezi ale proprietăților de echivalență a instrumentelor (în acest caz, recunoscătorii Rabin și Scott și expresiile regulate). Într-o primă parte se arată că fiecare limbă acceptată de un RSR îndeplinește anumite ecuații ale limbilor care pot fi rezolvate în mod unic, ducând la expresii regulate. Într-o secundă, pornind de la o expresie regulată, se identifică un RSR care acceptă limbajul pe care expresia îl identifică.
