Kleeneův teorém

Hlavní tezí Kleeneovy věty je: "Třídy regulárních množin a automatizační jazyky se shodují."

Formulace

Nechť  je libovolná abeceda. Jazyk je prvkem semiringu regulárních jazyků v abecedě tehdy a jen tehdy, když to umožňuje nějaký konečný automat.

Důkaz

Jakýkoli graf přechodu stavového automatu může být vždy reprezentován v normalizované formě, ve které je pouze jeden počáteční vrchol s pouze odchozími hranami a pouze jeden konečný vrchol s pouze příchozími hranami.

Na přechodovém grafu prezentovaném v normalizované podobě lze provést dvě redukční operace – redukci hran a redukci vrcholu – při zachování jazyka povoleného tímto přechodovým grafem. Každá operace zmenšení nemění jazyk rozpoznávaný přechodovým grafem, ale snižuje buď počet hran, nebo počet vrcholů.

Proto je každý jazyk automatu regulární množinou.
Pro každý regulární výraz R lze zkonstruovat konečný automat (případně nedeterministický), který rozpoznává jazyk specifikovaný R. Takové automaty budeme definovat rekurzivně.

Proto je každá běžná množina jazykem automatu. Věta byla prokázána.

Odkazy

Viz také

Literatura