Kleenes sætning

Hovedtesen i Kleenes teorem er: "Klasserne af regulære sæt og automatsprog falder sammen."

Ordlyd

Lad være  et vilkårligt alfabet. Et sprog er et element i semiring af regulære sprog i alfabetet , hvis og kun hvis det tillades af en eller anden endelig automat.

Bevis

Enhver tilstandsmaskine-overgangsgraf kan altid repræsenteres i en normaliseret form, hvor der kun er et indledende toppunkt med kun udgående kanter og kun et endeligt toppunkt med kun indkommende kanter.

På en overgangsgraf præsenteret i normaliseret form, kan to reduktionsoperationer udføres - kantreduktion og toppunktsreduktion - samtidig med at det sprog, der tillades af denne overgangsgraf, bevares. Hver reduktionsoperation ændrer ikke sproget, der genkendes af overgangsgrafen, men reducerer enten antallet af kanter eller antallet af hjørner.

Derfor er hvert automatsprog et almindeligt sæt.
For hvert regulært udtryk R kan der konstrueres en endelig automat (muligvis ikke-deterministisk), der genkender sproget specificeret af R. Vi vil definere sådanne automater rekursivt.

Derfor er hvert almindeligt sæt et automatsprog. Sætningen er blevet bevist.

Links

Se også

Litteratur