Automatas

1. a(a│b)* a
Autómata finito que empiece con una “a” seguido de cualquier combinación de “a” ó “b” y que termine con una “a”
2. ((ea)b*)b
Autómata que acepta una cadena “vacia” ó una “a” seguidade cualquier combinación de “b”
3. (a│b)*a(a│b)(a│b)
Cualquier número de “a” o “b” seguida de a que termine en “b”
4. A* ba* ba* ba*
Cualquier cantidad de “a” que terminen en “b”
5.(aa│bb)*((ab│ba) (aa│bb)* (ab│ba) (aa│bb)*)*
Cualquier combinación de “aa” o “bb” con cualquier combinación de “ab” o “aa” o “bb” pero no seguido de “ab”

Ejercicios de Compiladores
Para los lenguajes dadossobre ∑ = {a, b} construir una expresión regular de él y un Autómata Finito que lo acepte:

a) L = {w|w tiene un numero par de a′s}
b) L = {w|w tiene un numero impar de a′s}
c) L = {w|w tiene unnumero múltiplo de 3 de a′s}
d) L = {w| toda a en w está entre dos b′s}
e) L = {w| no hay dos a′s consecutivas en w}
f ) L = {w| w no contiene la subpalabra aa ni bb}Equivalencia entre AFD y AFN
La equivalencia entre AFD y AFN es clara entendiendo todo AFD como un caso particular de un AFN. En el otro sentido, a partir un AFN A=(Q,∑, ,q0,F) se puede construir otro AFDA'=(Q',∑, ', q0', F') equivalente (que acepte el mismo lenguaje), de la siguiente forma:
Q' = 2Q
q0' = {q0}
F' = { q' Ɛ Q' | q' ∩F ≠ 0}
'(q',a) =U(q Ɛq')(q,a) : q' ƐQ, a Ɛ∑

Figura 1. Autómatafinito no determinista del ejemplo 1.

Ejemplo 1. Dado el autómata de la figura 1, el proceso de construcción de un AFD equivalente parte del estado inicial {q0}, y determina el conjunto de estadosalcanzables con cada símbolo del alfabeto. De esta forma, por ejemplo, al considerar el símbolo a se alcanzan los estados {q0, q1, q2}.
Cada uno de los conjuntos de estados que aparezcan se consideracomo uno de los estados del AFD equivalente, determinándose para cada uno de ellos su función de transición. El proceso se repite mientras aparezcan nuevos estados. La figura 2 muestra la tabla de...