Lenguajes y autómatas I

UNIDAD 3.- AUTOMATAS FINITOS.

3.1 CONCEPTO DEFINICIÓN Y CLASIFICACIÓN DE AUTÓMATA FINITO (AF)

Un autómata finito (AF) o máquina de estado finito es un modelo computacional que realiza cómputos en forma automática sobre una entrada para producir una salida.

Este modelo está conformado por un alfabeto, un conjunto de estados y un conjunto de transiciones entre dichos estados. Su funcionamiento se basa en una función de transición, que recibe a partir de un estado inicial una cadena de caracteres pertenecientes al alfabeto (la entrada), y que va leyendo dicha cadena a medida que el autómata se desplaza de un estado a otro, para finalmente detenerse en un estado final o de aceptación, que representa la salida.

La finalidad de los autómatas finitos es la de reconocer lenguajes regulares, que corresponden a los lenguajes formales más simples según la Jerarquía de Chomsky.

Definición formal Formalmente:

E: alfabeto de entrada.
Q: conjunto de estados; es conjunto finito no vacío.
f: función de transición. f(p,a)=q
q0 : (perteneciente a Q) estado inicial.
F : (perteneciente a Q) conjunto de estados finales o de aceptación.

En el comienzo del proceso de reconocimiento de una cadena de entrada, el autómata finito se encuentra en el estado inicial y a medida que procesa cada símbolo de la cadena va cambiando de estado de acuerdo a lo determinado por la función de transición.

Cuando se ha procesado el último de los símbolos de la cadena de entrada, el autómata se detiene en el estado final del proceso. Si el estado final en el que se detuvo es un estado de aceptación, entonces la cadena pertenece al lenguaje reconocido por el autómata; en caso contrario, la cadena no pertenece a dicho lenguaje.

Note que el estado inicial de un autómata finito siempre es único, en tanto que los estados finales pueden ser más de uno, es decir, el conjunto puede contener más de un elemento. También puede darse el caso de que un estado final corresponda al mismo estado inicial.

CLASIFICACIÓN DE AF LOS AUTÓMATAS SE PUEDEN CLASIFICAR EN:

· Deterministas; Cada combinación (estado, símbolo de entrada) produce un solo estado.

· No Deterministas; Cada combinación (estado, símbolo de entrada) produce varios estados y además son posibles las transiciones con λ.

Los autómatas se pueden representar mediante tablas de transición o diagramas de transición.

REPRESENTACION:

TABLA	a	b
->p	q
*q	q3	r
q3		r
r	q3

Tablas de transición:
• Filas encabezadas por los estados( Q )
• Columnas encabezadas por los símbolos de entrada ( E )

Diagramas de transición:

• Nodos etiquetados por los estados(Q)
• Arcos entre nodos etiquetados con ( E )
• Q0 se señala con ->
• El estado final se señala con * o con doble circulo

Ejemplo: Sea el AFD1 = ({a,b}, {p,q,r}, f, p, {q}) donde f está

definida por:
f(p,a) = q f(p,b) = r
f(q,a) = q f(q,b) = r
f(r,a) = r f(r,b) = r

Escribir su tabla de transición y dibujar su diagrama de transición.
estados (Q): p, q, r
estado inicial: p
estado final: q

Bibliografia:

Enrique Alfonseca Cubero, Manuel Alfonseca Cubero, Roberto Moriyón Salomón." Teoría de autómatas y lenguajes formales". McGraw-Hill (2007). Capítulos 3 y 7

http://automatas-finitos.blogspot.com/

Maigualida Pérez Melgarejo

3.2 CONVERSIÓN DE AUTÓMATA FINITO NO DETERMINISTA A AUTÓMATA FINITO DETERMINISTA.

Todo AFND estricto, puede ser transformado a AFD utilizando un algoritmo que transforma los estados del AFND en nuevos estados que son subconjuntos de los estados originales y aplica a los mismos la clausura para confirmar la conexidad entre cada uno de los componentes y así eliminar el indeterminismo.

Sea un autómata finito estrictamente no determinista (AFND) definido por la 5-tupla A=<Q, T, g, F, q₀>, donde Q es el conjunto de estados, T el alfabeto de símbolos terminales, la relación de transiciones

1. A se transforma en A_AFD=<Q_A,T, g_A,F_A,q_0A>', tal que:

a. V_A=P(V)-{{}}, con P(V) que es el conjunto potencia de los vértices de A.

b. F_A={x | }.

c. g_A={<r,x,q> | }.

d. q_0A={q₀}

2. Luego se eliminan de A_AFD todos los estados y sus correspondientes transiciones inalcanzables desde el estado inicial q_0A.

Ejemplo

Véase el proceso de transformación de AFND a AFD del autómata A=<{q0,q1,f},{a,b},{<q0,a,q0>,<q0,b,q0>,<q0,a,q1>,<q1,b,f>},{f},q0>, que reconoce a las cadenas de as y bs que comienzan con cualquiera cantidad de estas letras y terminan forzosamente en ab.

Primero se obtiene autómata derivado A_AFD=<V_AFD,T_AFD,g_AFD,F_AFD,{q0}> a partir del conjunto potencia de los estados de A donde:

· V_AFD={{q0},{q1},{f},{q0,q1},{q0,f},{q1,f}, {q0,q1,f}}.

· T_AFD={a,b}.

· F_AFD={{f},{q0,f},{q1,f}, {q0,q1,f}}.

Luego se retiran los estados inaccesibles {q1}, {f}, {q1,f}, {q0,q1,f}, determinados mediante la clausura de {q0}, y queda:

· A_AFD={{q0,{q0,q1},{q0,f}},{a,b},{<{q0},b,{q0}>,<{q0},a,{q0,q1}>,<{q0,q1},a,{q0,q1}>,<{q0,q1},b,{q0,f}>,<{q0,f},a,{q0,q1}>,<{q0,f},b,{q0}>},{ {q0,f} },{q0}}.

Bibliografía:

https://www.ecured.cu/Transformaci%C3%B3n_de_aut%C3%B3mata_finito_no_determinista_a_aut%C3%B3mata_finito_determinista

Blanca Estela Reyes Castillo

3.3 REPRESENTACIÓN DE ER USANDO AFND.

ERs, AFDs y AFNDs son mecanismos equivalentes para denotar los lenguajes regulares. En estas tres secciones demostraremos esto mediante convertir ER→AFND → AFD → ER. Las dos primeras conversiones son muy relevantes en la práctica, pues permiten construirverificadores o buscadores eficientes a partir de ERs.

Existen algoritmos que relacionan la especificación de tokens -expresiones regulares-, con el reconocimiento de éstos -autómatas finitos-. Es posible dada una expresión regular obtener el AFD que reconozca las cadenas del lenguaje denotado por la expresión regular. También es posible obtener el AFND que reconozca el lenguaje representado por dicha expresión regular. El algoritmo que permite construir el autómata finito determinístico está fuera del alcance de estas notas (el alumno no tiene los prerrequisitos para su estudio en este curso). Sin embargo, el algoritmo utilizado para la construcción del autómata finito no determinístico AFND, es relativamente sencillo de aplicar, ya que se basa en reglas simples. Existen muchas variantes de este algoritmo denominado “Algoritmo de Thompson”.

Este algoritmo es dirigido por sintaxis, es decir, usa la estructura sintáctica de la expresión regular para guiar el proceso de construcción del autómata AFND. Supongamos que N(s)y N(t)son AFND’s para las expresiones regulares sy t,

respectivamente.

a) Para la expresión regular s | t(alternancia), construir el siguiente AFND, N(s|t):

b) Para la expresión regular st(concatenación), construir el AFND, N(st) :c)

c) Para la expresión regular s*, construir el AFND, N(s*) :

bibliografia

https://www.scribd.com/doc/226694899/Unidad-III-y-IV-Lenguajes-y-Automatas-i

3.4 MINIMIZACION DE ESTADOS EN UN AF.

Dos estados de un autómata finito determinista son estados equivalentes si al unirse en un sólo estado, pueden reconocer el mismo lenguaje regular que si estuviesen separados. Esta unión de estados implica la unión tanto de sus transiciones de entrada como de salida. Si dos estados no son equivalentes, se dice que son estados distinguibles. Un estado final con un estado no-final nunca serán equivalentes.

Un AFD está minimizado, si todos sus estados son distinguibles y alcanzables. Un algoritmo de minimización de AFD es el siguiente:

Eliminar los estados inaccesibles del autómata.

Construir una tabla con todos los pares (p, q) de estados restantes.

Marcar en la tabla aquellas entradas donde un estado es final y el otro es no-final, es decir, aquellos pares de estados que son claramente distinguibles.

Para cada par (p, q) y cada símbolo a del alfabeto, tal que r = δ(p,a) y s = δ(q,a):

Si (r, s) ya ha sido marcado, entonces p y q también son distinguibles, por lo tanto, marcar la entrada (p, q).

De lo contrario, colocar (p, q) en una lista asociada a la entrada (r, s).

Agrupar los pares de estados no marcados.

Luego del tercer paso, si la tabla creada queda completamente marcada, entonces el AFD inicial ya era mínimo.

finalmente se obtiene el autómata final, agrupando los estados b y f, así como c y g.

Ejemplo:

Dado un AFD M = (Q, Σ, δ, q0, F), se trata de encontrar un AFD M′ con L(M) = L(M′) y tal que M′ tenga el mínimo numero de estados posible. Para ello, el método consiste en encontrar todos los estados que son equivalentes, es decir, que son indistinguibles en el autómata. Por cada clase de estados equivalentes, el autómata mínimo necesitara un solo estado.

Dados dos estados q, q′ ∈ Q, q y q ′ son indistinguibles o equivalentes si para cualquier cadena w ∈ Σ ∗ se cumple una de las dos siguientes opciones:

· δ(q, w) ∈ F y δ(q ′ , w) ∈ F

· δ(q, w) 6∈ F y δ(q ′ , w) ∈ F 1

El método para minimizar un autómata consiste básicamente en encontrar todos los estados que son indistinguibles entre si y sustituirlos por un único estado. Para ello lo principal es averiguar que estados son distinguibles y cuales no.

El método para saber que estados son indistinguibles es el siguiente:

a. Si hay algún estado inalcanzable eliminarlo

b. (i := 0) Marcar todos los estados que pueden distinguirse con la cadena

vacía (es decir, todos los finales se pueden distinguir de los no finales).

c. (i := i + 1) Marcar como distinguibles q y q′

si con algún a ∈ Σ tenemos δ(q, a) y δ(q′, a) dos estados que ahora son distinguibles.

d. Si en el paso anterior se han distinguido nuevos estados, entonces volver

al paso c.

Bibliografia:

John E. Hopcroft, Rajeev Motwani, Jeffrey D.Ullman. "Introducción a la teoría de autómatas, lenguajes y computación" (3ª edición). Ed, Pearson Addison Wesley.

Sects. 2.1-2.2; Sects. 2.3-2.8; HMU, Chap. 4;HMU, Sects. 3-1-3.7

http://www.sc.ehu.es/jiwnagom/MAC1-ALF/MAC-archivos/Tema2-parte3.pdf

https://sites.google.com/site/tautomatasfinal/minimizacion.

Edgarda Santiago Reyes

3.5 APLICACIONES (DEFINICIÓN DE UN CASO DE ESTUDIO)

• Interruptor de luz

• Control de máquinas de bebidas

• Analizadores/generadores de palabras

• Control de las tareas de un robot

• Búsqueda y sustitución de palabras

• Tratamiento de masas de textos

• Analizadores léxicos de compiladores y traductores

• etc.

Máquina de bebidas:

1. Las bebidas cuestan 25 céntimos.

2. Monedas que admite la máquina:

1. De cuarto, 25 céntimos (Q).

2. Dimea, 10 céntimos (D).

3. Nickel, 5 céntimos (N).

3. La máquina acepta cualquier combinación

de monedas hasta 25 céntimos.

4. La máquina requiere la cantidad exacta.

Bibliografía:

http://www.sc.ehu.es/jiwnagom/MAC1-ALF/MAC-archivos/Tema2-parte3.pdf

Marisa Martínez Bautista

UNIDAD 2

Expresiones regulares.

2.1.- Definición formal de una ER.

Son patrones utilizados para encontrar una determinada combinación de caracteres dentro de una cadena de texto. En JavaScript, las expresiones regulares también son objetos. Estos patrones se utilizan en los métodos exec y test de RegExp, así como los métodos match, replace, search y split de String. En este capítulo se describe el uso y funcionamiento de las expresiones regulares en JavaScript.

Una expresión regular puede crearse de cualquiera de las dos siguientes maneras:

Utilizando una representación literal de la expresión regular, consistente en un patrón encerrado entre diagonales, como a continuación:

var re = /ab+c/;

La representación literal ofrece la compilación de la expresión regular cuando se carga el script donde se encuentra. Si la expresión regular permanece constante, utilizar esta forma puede mejorar en rendimiento.

Llamando a la función constructora del objeto RegExp, como a continuación:

var re = new RegExp('ab+c');

El uso de la función constructora ofrece la compilación en tiempo de ejecución de la expresión regular. Utilice la función constructora cuando sepa que el patrón de la expresión regular cambiará, o cuando desconozca el patrón y deba obtenerlo de otra fuente, como por ejemplo del usuario.

Una expresión regular ER sobre un alfabeto finito Σ se define recursivamente como sigue:

1. Para todo c ∈ Σ, c es una ER

2. Φ es una ER

3. Si E1 y E2 son ERs, E1 | E2 es una ER

4. Si E1 y E2 son ERs, E1 · E2 es una ER

5. Si E1 es una ER, E1 ⋆ es una ER

6. Si E1 es una ER, (E1) es una ER Cuando se lee una expresión regular, hay que saber qué operador debe leerse primero. Esto se llama precedencia.

Por ejemplo, la expresión a | b · c ⋆,

¿debe entenderse como

(1) la “⋆” aplicada al resto?

(2) ¿la “|” aplicada al resto?

(3) ¿la “·” aplicada al resto?

La respuesta es que, primero que nada se aplican los “⋆”, segundo los “·”, y finalmente los “|”.

Esto se expresa diciendo que el orden de precedencia es ⋆, ·, |.

Los paréntesis sirven para alterar la precedencia.

Por ejemplo, la expresión anterior, dado el orden de precedencia que establecimos, es equivalente a

Convengamos que en ambos operadores binarios se lee primero el de más a la izquierda (se dice que el operador “asocia a la izquierda”), pero realmente no es importante, por razones que veremos enseguida. Observar que aún no hemos dicho qué significa una ER, sólo hemos dado su sintaxis, pero no su semántica.

Bibliografía;

John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman (2001). Automata Theory, Language and Computation. Addison-Wesley Publishing.

Michael Sipser (1997). Introduction to the Theory of Computation. PWS publishing company.

Maigualida Pérez Melgarejo.

2.1. Definición formal de una ER.

Es utilizado como un lenguaje para describir patrones en texto que son sencillos pero muy útiles.

Dado un alfabeto Σ, una expresión regular sobre expresión regular sobre Σ se define de forma recursiva:

ER primitivo: Φ, λ, {a | a ЄЄЄ Σ Є}

Si α y β son ER, entonces son también ER: α + β (unión), α β (concatenación), α* (cierre), (α).

No existen otras reglas para la construcción de ER sobre Σ.

Ejemplo de uso.

Por ejemplo, la expresión regular: 01* + 10* denota todas las cadenas que son o un 0 seguido de cualquier cantidad 1's o una 1 seguida de cualquier cantidad de 0's.

Operaciones de los lenguajes:

Unión: Si L y M son dos lenguajes, su unión se denota por L U M.

Concatenación: La concatenación es: LM o L.M.

Cerradura (o cerradura de Kleene): Si L es un lenguaje su cerradura se denota por L *.

Si E es una expresión regular, entonces L(E) denota el lenguaje que define E. Las expresiones se construyen de la manera siguiente:

Las contantes y son expresiones regulares que representan a los lenguajes L (Q) = {Q} y L (Φ) L = Φ respectivamente.

Si a es un símbolo, entonces es una expresión regular que representan al lenguaje: L (a) = {a}.

Bibliografía:

http://10380054.galeon.com/u2.htm

Santiago Reyes Edgarda.

2.2.-Diseño en ER.

Unión o Alternativa: Consideremos dos lenguajes diferentes definidos sobre el mismo alfabeto L1 ⊂ W(∑) y L2 ⊂ W(∑). Se denomina unión de ambos lenguajes al lenguaje formado por las palabras de ambos lenguajes:

L1 U L2={ x | x ∈ L1 ó x ∈ L2}

Concatenación: Consideremos dos lenguajes definidos sobre el mismo alfabeto, L1 y L2. La concatenación o producto de estos lenguajes es el lenguaje L1 L2= { xy / x ∈ L1 y x ∈ L2} Las palabras de este lenguaje estarán formadas al concatenar cada una palabra del primero de los lenguajes con otra del segundo.

La concatenación de lenguajes con el lenguaje vació es ΦL = L Φ = Φ

Potencia de un lenguaje: Se define la potencia i-ésima de un lenguaje a la operación de concatenarlo consigo mismo i veces.

Li= LLL ....L

|------------|

Clausura positiva de un lenguaje: Se define la clausura positiva de un lenguaje L:

∞

L + = U L i

i=1

Lenguaje obtenido uniendo el lenguaje; con todas sus potencias posibles excepto Lº. Si L no contiene la palabra vacía, la clausura positiva tampoco

Cierre o Clausura de un lenguaje: Se define el cierre o clausura de un lenguaje L como:

∞

L* = U Li

i=0

Lenguaje obtenido uniendo el lenguaje con todas sus potencias posibles, incluso Lº. Todas las clausuras contienen la palabra vacía.

Existen tres operaciones básicas que se pueden realizar sobre las ER:

Selección de alternativas: Se indica con el operador |(barra vertical). Si r y s son ER, entonces r | s es una ER que define a cualquier cadena que concuerde con una r o una s, también se dice que r | s , es la unión de los lenguajes de r y s y lo podemos definir: L( r | s ) = L( r ) U L( s ). Esta operación se puede extender a más de dos ER.

Concatenación: Se indica con la yuxtaposición de las ER. Si r y s son ER, entonces rs es una ER que define a cualquier cadena que concuerde con la concatenación de r y s , esta operación la podemos definir: L(rs) = L(r)L(s).Esta operación se puede extender a más de dos ER.

Repetición o Cerradura: También se conoce con el nombre de cerradura de Kleene. Se indica con el operador *. Si r es una ER, entonces r* es una ER que define a las cadenas de caracteres representadas por la concatenación repetida de r en n veces, o sea que lo podemos definir como: L(r*) = L(r)*o también lo podemos definir como la unión infinita de conjuntos r :r* n = r 0 r 1 r 2...r n.

Bibliografía;

http://10380054.galeon.com/u2.htm

Marisa Martínez Bautista.

2.3.- Aplicación en problemas reales.

Rodolfo Rodríguez Medina

2.3 aplicaciones en problemas

Las expresiones regulares que facilitan la construcción de un compilador. A menudo se utiliza una expresión regular larga y compleja para validar la sintaxis de un programa. Si el código del programa no concuerda con la expresión regular, el compilador sabe que hay un error de sintaxis dentro del código.

Generalmente convierten la expresión regular a un autómata finito no determinista y después construyen el autómata finito determinista.

1.- Ejemplo:

Si ∑ = {a, b, c} entonces

∑² = {aa, ab, ac, ba, bb, bc, ca, cb, cc}

2.- Ejemplo:

Sea Ꞩ = {0, 1} y L ={01, 1} entonces

L³ = {010101, 01011, 01101, 0111, 10101, 1011, 1101, 111}

Bibliografías:

https://es.slideshare.net/AnelVeronicaUchihaLP/espresiones-regulares

https://slideplayer.es/slide/1875947/

Blanca Estela Reyes Castillo.

Lenguajes y autómatas I

lunes, 4 de marzo de 2019

lunes, 18 de febrero de 2019

Denunciar abuso