automatas

Construcción del autómata finito con transiciones ε
Si r es una expresión regular con n operadores y sin variables como operandos atómicos, existe un autómata finito no determinístico M contransiciones ε (AFND-ε) que acepta solamente aquellas cadenas que están en L(r). M tiene un estado final, no entran arcos al estado inicial y no salen arcos del estado final. r puede ser una expresión sinoperadores (∅, ε o un símbolo) o con operadores (+, ., *). Si r no tiene operadores, entonces:


Si r tiene operadores, se dan tres casos dependiendo de la forma de r:
1)r=r1 +r2 Sean M1 = y M2= , los autómatas correspondientes a r1
y r2. Se construye un nuevo autómata M que une a estos dos autómatas M1 y M2 agregando un estado inicial e0 y un estado final ef0; M = < E1 ∪ E2 ∪ {e0, ef0},A, δ, e0, {ef0}>. El estado inicial de M tiene transiciones ε a los estados iniciales de M1 y M2; los estados finales de estos autómatas tienen transiciones ε al estado final del autómata M.2)r=r1 . r2 Sean M1 = y M2 = , los autómatas correspondientes a r1
y r2. Se construye un nuevo autómata M, M = < E1 ∪ E2, A, δ, e01, {ef2}> que tiene como estado inicial al estado inicial de M1 y comoestado final al estado final de M2; tiene además un arco rotulado ε desde el estado final de M1 al estado inicial de M2.







3) r = r1* Sea M1 = el autómata correspondiente a r1. Seconstruye un nuevo autómata M, M = < E1 ∪ {e0, ef0}, A, δ, e0, {ef0}>; y se agregan arcos rotulados ε desde e0 al estado inicial de M1 y al estado final de M, y desde el estado final de M1 al estado inicialde M1 y a ef0.

Construcción del AFND a partir del AFND-ε
Dado un AFND-ε es posible construir un AFND equivalente sin transiciones vacías que reconoce el mismo lenguaje. Los estados del nuevoautómata son los estados importantes del AFND-ε y el estado inicial del AFND-ε. Se denominan estados importantes aquellos estados a los que llega un arco con un símbolo real como rótulo. El estado...