autómatas finitos deterministas y lenguajes formales

Autómatas Finitos Deterministas – Lenguajes

Formales

Sandy Rafael Garcia Mateo

Jeffry Gonzalez Garcia

Prof. Rina Familia

Temas a tratar

• Autómata Finito Determinista

• Definición Formal de AFD

• Lenguajes Regulares

• Propiedades de los lenguajes regulares

Autómata finito determinista

• El lenguaje que acepta un AFD(Autómata Finito Determinista) es el conjunto de palabras definidas sobre Σ(un alfabeto) que hacen que el autómata llegue a un estado final de aceptación.

Definición Formal

• Un autómata finito determinista (AFD) es una quíntupla

M = (Σ, Q, δ, q0, F)

donde

• Σ es un alfabeto finito.

• Q es un conjunto finito no vacío de estados, es decir, 0 < |Q| < ∞.

• δ es una función de transición:

δ : Q × Σ −→ Q ; δ(q, σ) = p

es decir, si el autómata se encuentra en el estado q y “lee” el símbolo σ va al estado p.

• q0 ∈ Q es el estado inicial.

• F ⊆ Q es el conjunto de estados finales.

Lenguajes Regulares

• Los lenguajes más sencillos que se considerarán son los lenguajes regulares, es decir, los que se pueden generar a partir de los lenguajes básicos, con la aplicación de las operaciones de unión, concatenación y estrella de Kleene un número finito de veces.

• Tomaremos el siguiente modelo, como base para ejemplificar las diferentes operaciones.

Lenguajes Regulares

• Ejemplo, modelo base:• Suponiendo que los dos autómatas siguientes sean

para el mismo alfabeto Σ = { x, y }:

Unión

• La unión de dos lenguajes regulares es otro lenguaje regular. Se utiliza la operación de unión de conjuntos; así, para el alfabeto Σ ={x,y} si L1 = {x,xy} y L2 = {yz,yy} entonces su unión será L1 È L2 = {x,xy,yz,yy }.

Propiedades de Unión

• 𝐿 = 𝐿1 ∪ 𝐿2 es regular, porque podemos construir una expresión regular para 𝐿 , teniendo las expresiones regulares para 𝐿1 y 𝐿2, más preciso: con 𝐿1 = 𝐿(𝛼) y 𝐿2 = 𝐿 𝛽 tenemos

• 𝐿 = 𝐿((𝛼 + 𝛽))

Unión – Ejemplo

Concatenación

• Sean dos palabras x e y definidas sobre el alfabeto Σ. La concatenación de x e y, denominada “xy”, es una palabra que contiene todos los símbolos (de derecha a izquierda) de x seguidos de los símbolos de y (de derecha a izquierda).

Propiedades de Concatencación

• 𝐿 = 𝐿1. 𝐿2 es regular, porque podemos construir una expresión regular para 𝐿 , teniendo las expresiones regulares para 𝐿1 y 𝐿2, más preciso: con 𝐿1 = 𝐿(𝛼) y 𝐿2 = 𝐿 𝛽 tenemos

• 𝐿 = 𝐿(𝛼 𝛽)

Concatenación – Ejemplo

Estrella de Kleene

• La estrella de Kleene de cualquier lenguaje regular también es regular. Se caracteriza por que se utiliza solo un lenguaje en lugar de dos. Se logra formando todas las concatenaciones de cero (cadena vacía) o más cadenas del lenguaje que se amplía. La operación se representa con el asterisco supraíndice ( * ).

Propiedades de Estrella o Clausura

• 𝐿 = 𝐿1 ∗ es regular, porque podemos construir una expresión regular para 𝐿 , teniendo la expresión regular para 𝐿1, más preciso: con 𝐿1 = 𝐿 𝛼 tenemos

• 𝐿 = 𝐿 (𝛼 ∗)

Estrella de Kleene - Ejemplo

1 2

Intersección

• La intersección de varios lenguajes regulares es otro lenguaje regular. Se utiliza la operación de intersección de conjuntos; así, para el alfabeto Σ ={x,y} si L1 = {x,xy,yy}, L2 = {yz,yy} y L3 = {y,yy} entonces su intersección será L1 Ç L2 ÇL3 = {yy}.

• Para ejemplificar la intersección, utilizaremos un modelo distinto.

Propiedades de Intersección

• 𝐿 = 𝐿1 ∩ 𝐿2 es regular, porque con las reglas de DeMorgan obtenemos 𝐿 = 𝐿1 ∪ 𝐿2 = 𝐿1 ∪ 𝐿2, Complemento y unión producen lenguajes regulares, como visto antes. Dicha construcción es bastante laborosa, abajo vemos una construcción directa y simple.

Intersección - Ejemplo

• Para diseñar el autómata finito que admite el lenguaje intersección aplicamos:

• S' será el producto cartesiano de todos los conjuntos de estados originales S' = S1 x S2 x S3 x...x Sn.

• En nuestro caso particular, S1 = { 1, ,2 } y S2 = { 3, 4 } el producto cartesiano s' = S1 | x| S2 = { (1,3), (1,4), (2,3), (2,4) }.

• El alfabeto tiene que ser el mismo para todos los autómatas. S' = S = { x, y }.

• El estado inicial será aquel que está formado por los estados iniciales originales: i' = ( i1, i2, i3,..., i n ).

• En nuestro caso, es el par (1,3).

• Los estados de aceptación serán aquellos que están formados por estados de aceptación originales. F' = (F1,F2,F3,..., Fn).

• En nuestro caso solo tenemos un estado de aceptación en f', que es el par (2,3)

Intersección - Ejemplo

Propiedades de Complemento y Diferencia

Referencias

• http://www.aconute.es/computacion/automatasFinitos/ejemplo_opers.html

• https://automaton.wikispaces.com/2.3.+Definición+formal+de+autómatas+finitos

• http://www.aconute.es/computacion/automatasFinitos/ta_cap1_6.html

• http://www.virtual.unal.edu.co/cursos/ciencias/2001018/lecciones/PDFs/Cap1/Cap1b.pdf

• http://trevinca.ei.uvigo.es/~formella/doc/talf05/talf/node38.html