Nothing Special   »   [go: up one dir, main page]

Vés al contingut

Algorisme de Kleene

De la Viquipèdia, l'enciclopèdia lliure

En informàtica teòrica, en particular en teoria de llenguatges formals, l'algorisme de Kleene transforma un autòmat finit no determinista (AFND) en una expressió regular. Juntament amb altres algorismes de conversió, estableix l'equivalència de diversos formats de descripció per llenguatges regulars. Presentacions alternatives del mateix mètode inclouen el "mètode d'eliminació" atribuït a Brzozowski i McCluskey, l'algorisme de McNaughton i Yamada, i l'ús del lema d'Arden.[1]

Descripció de l'algorisme

[modifica]

Segons Brut i Yellen (2004),[2] l'algoritme pot ser remuntat a Kleene (1956).[3] Una presentació de l'algorisme en el cas de l'autòmat determinista finit (ADF) és donat a Hopcroft i Ullman (1979).[4] La presentació de l'algorisme per AFNDs a sota segueix Brut i Yellen (2004).

Donat un autòmat finit no determinista , amb el seu conjunt d'estats, l'algorisme computa els conjunts de totes les entrades que porten de l'estat a sense passar per cap estat superior a . Aquí, "passar per un estat" vol dir entrar-hi i sortir-ne, així que ambdós i poden ser superiors a , però no cap estat intermedi. Cada conjunt és representat per una expressió regular; l'algorisme els computa pas a pas per . Com no hi ha cap estat superior a , l'expressió regular representa el conjunt de totes les entrades que porten del seu estat inicial a . Si és el conjunt d'estats finals, l'expressió regular representa el llenguatge acceptat per .

Les expressions regulars inicials, per a , es computen de la següent manera per a :

on

i com segueix per a :

on

És a dir, representa tots els símbols d'entrada que causen una transició d' a , i també incloem quan .

Seguidament, en cada pas les expressions es calculen a partir de les anteriors mitjançant:

Una altra manera d'entendre el procediment de l'algorisme és com un "mètode d'eliminació", on els estats de a s'eliminen successivament: quan s'elimina l'estat , l'expressió regular , que descriu les paraules d'entrada que generen un camí de l'estat a l'estat , és reescrita dins a fi de tenir en compte la possibilitat de passar per l'estat "eliminat" .

Per inducció en , es pot veure que la longitud[5] de cada expressió és com a màxim símbols, on denota el nombre de caràcters dins l'alfabet . Per tant, la longitud de l'expressió regular que representa la llengua acceptada per és com a màxim   símbols, on denota el nombre d'estats finals. Aquest creixement exponencial és inevitable, ja que existeixen famílies d'AFDs pels quals qualsevol expressió regular equivalent ha de ser de mida exponencial.[6]

A la pràctica, la mida de l'expressió regular obtinguda per l'algorisme pot ser molt diferent depenent en l'ordre en què es consideren els estats, i.e. l'ordre amb el qual són numerats de a .

Exemple

[modifica]
Autòmat finit determinista (AFD) de l'exemple

L'autòmat donat a l'esquema pot ser descrit com amb

  • el conjunt d'estats,
  • l'alfabet d'entrada,
  • la funció de transició amb , , , , , ,
  • l'estat inicial,
  • el conjunt d'estats finals o d'acceptació.

L'algorisme de Kleene computa les expressions regulars inicials de la següent forma:

Seguidament, les es computen a partir de les pas a pas per . S'utilitzen igualtats de l'àlgebra de Kleene per a simplificar les expressions regulars tant com sigui possible.

Pas 0

Pas 1

Pas 2

Com és l'estat inicial i és l'únic estat final, l'expressió regular denota el conjunt de totes les paraules d'entrada acceptades per l'autòmat.

Referències

[modifica]
  1. McNaughton, R.; Yamada, H. IRE Transactions on Electronic Computers, EC-9, 1, 3-1960, pàg. 39–47. DOI: 10.1109/TEC.1960.5221603. ISSN: 0367-9950.
  2. Jonathan L. Gross and Jay Yellen. Handbook of Graph Theory. CRC Press, 2004 (Discrete Mathematics and it Applications). ISBN 1-58488-090-2.  Here: sect.2.1, remark R13 on p.65
  3. Kleene, Stephen C. Automata Studies, Annals of Math. Studies, 34, 1956. Here: sect.9, p.37-40
  4. John E. Hopcroft, Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979. ISBN 0-201-02988-X.  Here: Section 3.2.1 pages 91-96
  5. More precisely, the number of regular-expression symbols, "ai", "ε", "|", "*", "·"; not counting parentheses.
  6. Gruber, Hermann; Holzer, Markus Automata, Languages and Programming, 5126, 2008, pàg. 39–50. DOI: 10.1007/978-3-540-70583-3_4.. Theorem 16.