Kleenes teorem

Huvudtesen i Kleenes teorem är: "Klasserna av vanliga uppsättningar och automatspråk sammanfaller."

Formulering

Låt vara  ett godtyckligt alfabet. Ett språk är en del av sammansättningen av vanliga språk i alfabetet om och bara om det tillåts av någon ändlig automat.

Bevis

Vilken tillståndsmaskinövergångsgraf som helst kan alltid representeras i en normaliserad form där det bara finns en initial vertex med endast utgående kanter och endast en slutlig vertex med endast inkommande kanter.

På en övergångsgraf som presenteras i normaliserad form kan två reduktionsoperationer utföras - kantreduktion och vertexreduktion - samtidigt som språket som tillåts av denna övergångsgraf bevaras. Varje förminskningsoperation ändrar inte språket som känns igen av övergångsgrafen, utan minskar antingen antalet kanter eller antalet hörn.

Därför är varje automatspråk en vanlig uppsättning.
För varje reguljärt uttryck R kan en finit automat (eventuellt icke-deterministisk) konstrueras som känner igen språket specificerat av R. Vi kommer att definiera sådana automater rekursivt.

Därför är varje vanlig uppsättning ett automatspråk. Teoremet har bevisats.

Länkar

Se även

Litteratur