Unidad N°4 Flashcards
(7 cards)
No determinismo y autómatas
la presencia de múltiples opciones posibles en la función de transición. Esto es, estando el AF en un cierto estado y ante una cierta señal de entrada, el desempeño del autómata admite múltiples posibilidades.
AFND = (ΣE, Q, q0, A, f)
y su característica distintiva está en la definición de las transiciones, que aquí no es más una función de estado a estado, sino una relación de transición, tomando la forma:
f: Q x ΣE → P(Q)
Transiciones Lambda
opción λ se considera de la misma forma que si se tratara de una transición convencional ante una cierta entrada e(e)ΣE. Es así que para contemplarlas se incorpora una columna adicional a la relación f a fin de considerar los pares (q, λ) y se cada estado tiene su propia transición λ que cicla sobre sí mismo.
f: Q x (ΣE u {λ}) → P(Q)
A todos los pares de estados que están vinculados por una transición λ es conveniente reunirlos en un conjunto T denominado relación de transición λ
T = {(p, q) / q e f (p, λ)} u {(q, q) / q e Q}
Extensión al tratamiento de palabras en AFND
La transición extendida f^e para reconocer cadenas o palabras puede inducirse a partir de un razonamiento parecido a la función de transición extendida para el AFD en el capítulo anterior, solo sumamos transiciones λ. Se obtiene una relación que queda definida como:
f^e : Q x (ΣE u {λ})* → P(Q)
Equivalencia con autómatas finitos deterministas
Al tratarse la equivalencia entre autómatas finitos, se destacan los dos teoremas que se enuncian a continuación.
Teorema 1
Todo AFND -λ puede ser redefinido como un AFND equivalente y, para ello, se deben eliminar sus transiciones λ.
Teorema 2
Por cada AFND, siempre existe un AFD que acepta el mismo lenguaje y estos dos autómatas se
dice que son equivalentes.
Caso 1
un AFND donde no hay transiciones λ. En un cierto estado, q y ante una entrada e, el AFND tiene la posibilidad a pasar a cualquiera de los estados pertenecientes al subconjunto f(q, e) y actúa como si se encontrara en cualquiera de ellos.
Ésta se considerará aceptada si el subconjunto de estados alcanzado incluye entre sus miembros a algunos de los estados que pertenecen a conjunto de estados de aceptación.
Caso 2
Se considera el caso de un AFND-λ, es decir que no han sido previamente eliminadas las transiciones λ y el procedimiento es el siguiente:
a. Reconocer el estado inicial co = f(qo, λ) = {p / qoTp}.
b. Definir nuevos estados ci = f ’(ck, e) para todo e(ΣE {λ}) y k < i.
c. Para todos los casos en que ci = {…, qn , …} y qnA se reconoce que ci(e)A’.
Definición de gramáticas regulares a partir de autómatas
Dado un AFD = (Σ, Q, q₀, A, f), la gramática que genera el mismo lenguaje que acepta el autómata, será G = (Σ, Q, q₀, P), donde el conjunto de reglas de reescritura queda definido como:
P = { X := aY / f(X, a) = Y } ∪ { X := a / f(X, a) = Y, Y ∈ A }
y se agrega q₀ := λ si q₀ ∈ A;
X, Y, q₀ ∈ Q, a ∈ Σ, A ⊆ Q.
Definición de autómatas a partir de gramáticas regulares
Dada la gramática regular G = (Σ_T, Σ_N, S, P), el autómata finito que acepta el mismo lenguaje que genera la gramática será:
AF = (Σ_T, Σ_N ∪ {A}, S, {A}, f)
donde A es un nuevo símbolo que no estaba en Σ_N y
f(X, a) = Y si X := aY está en P,
y f(X, a) = A si X := a está en P,
con X, Y, S ∈ Σ_N, a ∈ Σ_T.
La regla de producción S := λ incorpora la transición f(S, λ) = A.
Deben considerarse que:
- la existencia en la gramática de una regla de producción S:=lambda convierte al autómata asociado en AFND-lambda
- para el caso de que la gramática sea lineal por izquierda será necesario convertirla previamente a lineal por derecha, aplicando el procedimiento que es definido a continuación.
Método o Algoritmo de Thompson:
traduce cada parte de la definición de una expresión regular en un autómata que acepta el mismo lenguaje denotado por ella.
Recordemos que la definición de una expresión regular tiene una parte básica (, , a, siendo a cualquier símbolo del alfabeto) y una parte recursiva (E+F, E°F, E*, (E), siendo E y F expresiones regulares).
En los siguientes puntos, se trabajará siempre suponiendo que las expresiones regulares están describiendo un lenguaje sobre algún alfabeto Σ y, en cada caso, se construirá un autómata
finito AF = (Σ, Q, q0, A, f) mostrando su grafo dirigido.
