Amostrar código-fuonte de Spresson Regular

== Teorie de lenguaiges formales ==
Spressones regulares puoden ser spressas atrabeç de la [[lenguaige formal|teorie de lenguaiges formales]]. Eilhas cunsisten de custantes i ouperadores que denotan cunjuntos de cadeias de carateres i ouparaçones subre esses cunjuntos, respetibamente. Dado un [[alfabeto]] fenito Σ, las seguintes custantes son defenidas:
* (''[[cunjunto bazio]]'') {{Unicode|∅}} denotando l cunjunto {{Unicode|∅}}
* (''cadeia de carateres bazie'') ε denotando l cunjunto {ε}
* (''literal'') ''la'' an Σ denotando l cunjunto {''la''}

Las seguintes ouparaçones son defenidas:
* (''cuncatenaçon'') ''RS'' denotando l cunjunto { αβ | α an ''R'' i β an ''S'' }. Por eisemplo, {"''ab''", "''c''"}{"''d''", "''ef''"} = {"''abd''", "''abef''", "''cd''", "''cef''"}.
* (''altarnáncia'') ''R|S'' denotando l cunjunto ounion de ''R'' i ''S''. Usa-se ls simblos {{Unicode|∪}}, {{Unicode|+}} ó {{Unicode|∨}} para altarnáncia al ambés de la barra bertical. Por eisemplo, {"''ab''", "''c''"}{{Unicode|∪}}{"''db''", "''ef''"} = {"''ab''", "''c''", "''db''", "''ef''"}
* (''[[Fecho de Klene]]'') ''R''* denotando l menor [[superconjunto]] de ''R'' que cuntén ε i ye [[Fechamiento|cerrado]] sob cuncatenaçon. Esse ye l cunjunto de todas las cadeias de carateres que puoden ser custruídas al cuncatenar zero ó mais cadeias an ''R''. Por eisemplo, {"''ab''", "''c''"}* = {ε, "''ab''", "''c''", "''abab''", "''abc''", "''cab''", "''c''", "''ababab''", "''abcab''", ... }.

Las custantes i ls ouperadores arriba forman la [[álgebra de Klene]].

Para eibitar parénteses, ye assumido que l fecho de Klene ten la maior prioridade, depuis la cuncatenaçon i por fin l'altarnáncia. Se nun houbir ambiguidades, ls parénteses puoden ser omitidos. Por eisemplo, <code>(ab)c</code> puode ser scrito cumo <code>abc</code>, i <code>la|(b(c*))</code> puode ser scrito cumo <code>la|bc*</code>.

;Eisemplos:
* <code>la|b*</code> denota {ε, ''la'', ''b'', ''bb'', ''bbb'', ...}
* <code>(la|b)*</code> denota l cunjunto de todas las cadeias de carateres que cuntén ls símbols ''la'' i ''b'', ancluindo la cadeia bazie: {ε, ''la'', ''b'', ''aa'', ''ab'', ''ba'', ''bb'', ''aaa'', ...}
* <code>ab*(c|ε)</code> denota l cunjunto de cadeias de carateres ampeçando cun ''la'', anton cun zero ó mais ''b''s i oupcionalmente cun un ''c'': {''la'', ''ac'', ''ab'', ''abc'', ''abb'', ...}

La defeniçon formal de spressones regulares ye cuncisa i eibita l'outelizaçon de ls quantificadores redundantes <code>?</code> i <code>+</code>, que puoden ser spressados respetibamente por <code>(la|ε)</code> i <code>aa*</code>. Por bezes l'ouperador de cumplemiento ~ ye adicionado;  ~''R'' denota l cunjunto de las cadeias de carateres de Σ* que nun stan an ''R''. Esse ouperador ye redundante, i puode ser spressado usando outros ouperadores, anque de la cumputaçon para tal repersentaçon ser cumplexa.

Spressones regulares puoden spressar [[lenguaige regular|lenguaiges regulares]], la classe de lenguaiges aceita por un [[Máquina de stado fenito|outómato fenito]]. Antretanto, hai ua defrença seneficatiba na cumpataçon. Alguas classes de lenguaiges regulares puoden ser çcritas solamente por outómatos que crecen sponencialmente an tamanho, anquanto l tamanho de las spressones regulares requeridas solo puode crecer linearmente. Spressones regulares corresponden al Tipo-3 de las [[gramática formal|gramáticas]] de la [[Hierarquia de Chomsky]]. Por outro lado, eisiste un mapeamiento simples de spressones regulares para máquinas de stado fenito nó-determinísticas que nun lieba al crecimiento çgobernado de l tamanho. Por essa rezon, essas máquinas nun determinísticas son giralmente ousadas cumo repersentaçon altarnatiba de las spressones regulares.

Ye possible screbir un [[algoritmo]] que, para dues spressones regulares dadas, decide se las lenguaiges çcritas son eissencialmente eiguales. Reduç-se cada spresson na máquina de stado fenito mínima, i detremina-se se ambas las máquinas mínimas son [[eisomorfismo|eisomórficas]] (eiquibalentes).

Bal notar que dibersas amplementaçones de spressones regulares amplementan funcionalidades que nun puoden ser spressadas na álgebra de Klene; ber [[#Padrones para lenguaiges nun regulares|ambaixo]] mais subre l'assunto.