TEMA 3 MECANISMOS REGULARES. LEXICOGRAFÍA 3.1.- Lenguaje regular Un lenguaje regular es un lenguaje formal que puede ser definido por medio de un mecanismo regular, son mecanismos regulares: las expresiones regulares, las gramáticas regulares (de tipo 3) y los autómata finitos (o regulares). El léxico de un lenguaje de programación es un lenguaje regular y como tal se puede definir por medio de un mecanismo regular. Los lenguajes regulares son interesantes ya sea desde un punto de vista teórico como práctico. Teórico - los lenguajes regulares forman el menor conjunto de lenguajes formales que es cerrado con respecto de los operadores (´*´, ´.´ , ´|´) Práctico – los lenguajes regulares pueden ser especificados por mecanismos regulares que permiten simplificar y facilitar la construcción de analizadores léxicos (AL); programas que analizan un texto y extraen los lexemas de que consta 3.2 Expresiones regulares. Una expresión regular es una notación (descripción), que permite de manera precisa y finita especificar los lenguajes regulares. También puede definirse como un metalenguaje para especificar lenguajes regulares. - Descripción de las expresiones regulares básicas: Εl símbolo ∅ es una expresión regular que describe el lenguaje {}, lenguaje vacío Εl símbolo ε es una expresión regular que describe el lenguaje { ε }, lenguaje formado por la palabra vacía Para todo símbolo a ∈ ∑, a es una expresión regular que describe el lenguaje { a }, lenguaje formado por la palabra a. Al ser los lenguajes regulares el menor conjunto que es cerrado con respecto de los operadores (´*´, ´.´ , ´|´) y, sabiendo que las expresiones regulares básicas son: ∅, ε, a ∀a∈ ∑ podemos afirmar que la construcción de las expresiones regulares se pueden realizar a partir de la relación entre los operadores anteriores y los operandos que forman las expresiones regulares básicas. - Operaciones con expresiones regulares Sean α,β dos expresiones regulares: α|β es una nueva expresión regular, que denota el lenguaje L (α|β) = L(α) | L(β) a| ε es una expresión regular, que denota el lenguaje L (a|ε) = L(a) | L(ε) = {a}|{ε}={a,ε} α.β es una nueva expresión regular, que denota el lenguaje L (α.β) = L(α) . L(β) a. ε es una expresión regular, que denota el lenguaje L (a. ε ) = L(a).L(ε ) = {a}.{ε}={a} α* es una nueva expresión regular, que denota el lenguaje L (α*) = (L (α) )* a* es una nueva expresión regular, que denota el lenguaje L (a*) = (L (a) )* = {a}* = {ε, a, ..} Los anteriores operadores tienen el siguiente orden de precedencia en su ejecución, de mayor a menor: `*´, `.´ y `|´ , siendo (`.´, `|´ ) binarios mientras que (`*´) es unario que precede al operando. Esta precedencia puede ser modificada con el uso de los paréntesis (), teniendo mayor precedencia desde el interior hacia el exterior. - Lenguaje denotado o descrito por una expresión regular: Toda expresión regular α está definida sobre un alfabeto Σ, y denota o describe un lenguaje L(α) ⊆ Σ* L (a.b|c*) = L (a.b) | L(c*) = L ( (a).(b)) | (L(c))* = {a}.{b}|{ε, c, cc,…} = {ab, ε, c, cc,…}

1

L (a.(b|c*)) = L(a) L(b|c*) = L(a).L( (b) | (L(c)*) = {a}.({b} | (L(c))*) = {a}.({b} | {ε, c, cc,…}) = { ab,a, ac, acc,…} Dos expresiones regulares se dice que son equivalentes, si describen el mismo lenguaje. Las siguientes expresiones regulares se dice que son equivalentes, puesto que describe el mismo lenguaje. ab|c*⇔ab|c.c*| ε - Propiedades de los operadores que pueden formar parte de una ER Existen una serie de propiedades asociadas a los operadores que pueden intervenir en una ER. Estas propiedades permiten la transformación de una ER hasta encontrar otra equivalente. Propiedades que cumple el operador (|) unión de ER : Sean α , β, δ ∈ ER, se cumplen las siguientes propiedades: Operación cerrada P. idempotente P. conmutativa P. asociativa E. neutro

α|β=δ α|α=α α | β = β| α α | (β | δ) = ( α | β ) | δ α | ∅ =∅| α

Propiedades que cumple el operador (.) concatenación de ER : Sean α , β, δ ∈ ER, se cumplen las siguientes propiedades : Operación cerrada P. asociativa E. neutro P distributiva

α.β=δ α . (β . δ) = ( α . β ) . δ α.ε =ε|α=α α . (β | δ) = ( α . β )|( α. δ) (α | β) δ = ( α . δ) |( β . δ)

Propiedades de la operación estrella (*) ε *= ε ; φ*= ε ; α . α* = α*. α ; α*. α*= α* ; (α*)*= α* ; (α| ε )*= α* (α | β)* = (β*| α*)* ; (α | β)* = ( α*. β*)*= ( α*. β)* α* ; α( β α)*= ( α. β)* α - Expresiones regulares extendidasCon el fin de simplificar la representación de las expresiones regulares se pueden utilizar otros operadores, entre los que podemos destacar: +, ?, y [] α+ es una nueva expresión regular, que denota el lenguaje L(α+) = (L(α))+ a+ es una expresión regular, que denota el lenguaje L(a+) = (L(a))+ = {a}+ = {a,aa,…} α? es una nueva expresión regular, que denota el lenguaje L(α?) = (L(α))? = L(α) | {ε} a? es una expresión regular, que denota el lenguaje L(a? ) = (L(a))? = L{a}|{ε} = {a | ε} [α] es una nueva expresión regular, que denota el lenguaje L([α] ) = (L([α] )) = {α1, α2,..} [a-z] es una nueva expresión regular, que denota el lenguaje L([a-z] ) = (L[a,b,..]) ={a,b,c..} Otras propiedades Φ+= ϕ ε | α+= α* α*. α= α+ α+?= α* ; α*?= α* ; α*| α+= α* (α* α+)= α+ (α+)* = α* (α*)+ = α* α ?= ( α| ε ) α*= α0| α1| α2| ……αn| αn+1 = α0| α(α0| α1| α2| ……αn ) = α0| α α* α*= ε | α α* Regla de inferencia importante para conocer el concepto de ecuación característica o fundamental. ω= α*. β == α ω| β ω= (ε | α α*). β = β | α α* β= β | α ω

2

- Definiciones regulares Es una forma de denominar una expresión regular. A veces es conveniente darle un nombre significativo a una expresión o subexpresiones y poder utilizar dichos nombres como si fueran símbolos (expresión regular) para hacerla más legible Sea Σ el alfabeto de las palabras del lenguaje que se quiere describir con la expresión regular. Una definición regular defi es una secuencia de definiciones de la forma: def1 → exp1 def2 → exp12 …………. defn → expn las expi están definidas sobre Σ ∪{ def1 def2…. defn} Describir con palabras qué lenguaje representan las siguientes expresiones regulares: Identificador → (letra | numero) (letra | numero| _)* letra → a| b| ........z| A|.......| Z numero → 0| 1.....| 9 Expresiones regulares y gramáticas regulares Las expresiones regulares y las gramáticas regulares son dos mecanismos regulares equivalentes, que especifican lenguajes regulares. Por lo tanto, todo lenguaje regular puede ser definido (descrito) por una expresión regular o definido (generado) por una gramática regular equivalente. Ejemplos de lenguajes formales regulares definidos sobre el alfabetos Σ = {a, b}: L1 = {}= ∅, es un lenguaje regular , puede ser definido por una ER = ∅ ⇔ una G tipo3 S→A L2 = { ε }, es un lenguaje regular , puede ser definido por una ER= ε ⇔ una G tipo3 S→ε L3 = {a, b}, es un lenguaje regular , puede ser definido por una ER= a | b ⇔ una G tipo3 S→a |b L4 = {a, ab, ε}, es un lenguaje regular, puede ser definido por una ER= a|ab|ε ⇔ una G tipo3 S→a |ab| ε L5 = {an, n ≥ 0}, es un lenguaje regular, puede ser definido por una ER= a* ⇔ una G tipo3 S→aS| ε L6 ={an bm | n, m ≥ 0}={a0b0, a0b1,… .}= {εε, εa, εb …}={ ε,a, b,…} es un lenguaje regular , puede ser definido por una ER= a*b* ⇔ una G tipo3 P: S → aA| bB |ε , A → Aa |ε |bB , B →Bb |ε L7 ={palabras formadas por un número impar de aes}={ a, ba, ab, bab, aaba,…} , es un lenguaje regular , puede ser definido por una ER = a b*(ab* ab*)* ⇔ una G tipo3 Σ*= {lenguaje universal} ER= (a|b)*, es un lenguaje regular , puede ser definido por una G tipo3 S → aS| bS |ε L9 ={an bn | n ≥ 0}={a0b0, a1b1,… .}= {εε, ab, aabb …}={ ε, ab, b,…} no es un lenguje regular, no hay una ER que lo denote o gramática de tipo 3 equivalente que lo genere 3.3 Aplicación de las ER Las expresiones regulares son utilizadas en la gran mayoría de las aplicaciones informáticas, entre otras tenemos las siguientes: - Sistemas de recuperación de textos en lenguajes de consulta de base de datos - Búsqueda dentro de un contexto- comandos grep, egrep y fgrep del sistema UNIX, que a través de la descripción de una ER se puede buscar una determinada información -Construcción de analizadores léxicos, a partir de la especificación de ER, facilitando la implementación de la primera fase de un compilador. - Comparación de archivos dentro de un repositorio - Búsqueda de patrones

3

Ejemplos simples de expresiones regulares - Lenguajes que denotan las siguientes expresiones regulares: 0*

- Cadenas de ceros de cualquier longitud

(0|1)*- Cadenas binarias de 0 y 1 de cualquier longitud (10)* - Cadenas binarias donde cada 1 va seguido de un 0, ó es ε (0|1)*1(1|0)* - Cadenas binarias con al menos un 1 (1|10)* - Cadenas binarias que no tienen 2 ceros consecutivos, ó es ε 1(0|1)*1 - Cadenas binarias que empiezan y terminan en 1 1*01*01* - Cadenas binarias que tienen dos ceros (0|1)*00(1|0)* - Cadenas binarias que tienen la subsecuencia 00 - Dada la descripción de los siguientes lenguajes definidos sobre el alfabeto Σ={0, 1}), encontrar las expresiones regulares que los denotan. Cadenas binarias que acaben en 0 - (1|0)*0 Cadenas con sólo un 0 - 1*01* Cadenas binarias que no contienen "000" - ((1*|0)(1*|0)1)* Cadenas que si tienen un 1 va precedido y seguido de un 0 - (0+1)*0+ Cadenas que tienen un número impar de 1´s - 0*1(0*10*1)*0* - Un conjunto C es cerrado con respecto a la operación # si: ∀x, y∈ C, x#y∈C

4

Ejercicio 1 1.

2.

Razonar si son equivalentes o no las siguientes dos expresiones regulares: •

(a | ε) (ba+)*

•

(ba | a)*

Razonar si son equivalentes o no las siguientes expresiones regulares: •

(aa*)*b

•

(aa*)((aa*)*b) | b

- Para demostrar que no son equivalentes habrá que obtener al menos una palabra que quede denotada en una y no en la otra. - Para demostrar que son equivalentes habrá que hacerlo obligatoriamente mediante las propiedades de las expresiones regulares. De forma que partiendo de ambas y realizando los pasos según dichas propiedades, se alcance la misma expresión regular. Ejercicio 2 1.

Simplificar, detallando todos los pasos, la siguiente expresión regular: (( a* | ε )+ aa ) | ( ε ( aa+a))

2. Justificar de forma razonada si cada uno de los pasos que se realizan a continuación para simplificar la expresión regular a ( a* | a )* son correctos o no. a ( a* | a )* = ( a+ | aa )* = ( a+ ) * = a+ Ejercicio 3 Representar una expresión regular para cada uno de los siguientes lenguajes. Σ = {a, b, _ }. Palabras que como máximo pueden tener dos símbolos de subrayado consecutivos. Σ = {a, b, _ }. Palabras que no finalizan en la subpalabra a_ Σ = {a, b, c }. Palabras en las que el número de símbolos b más el número de símbolos c es 3. Σ = {a, b}. El lenguaje universal menos dos palabras: ε y a. Σ = {a, b}. Palabras que finalizan por el símbolo b y tienen un número par de símbolos b en total. Σ = {a, b}. Palabras que no contienen la subpalabra aa ni bb. Ejercicio 4 Crear una ER que denote los siguientes lenguajes:

a) Los comentarios en el lenguaje de programación Pascal se escriben de la siguiente manera: Comienzan por los símbolos (* y terminan por *). Si llamamos símbolo a cualquier carácter ASCII menos ‘*’ y ‘)’, en el interior del comentario se puede escribir cualquier cantidad de símbolos, incluyendo ninguno. Pero además, dentro del comentario se pueden usar los caracteres ‘*’ y ‘)’ siempre y cuando no haya un ‘*’ seguido de un ‘)’, en cuyo caso se interpretaría como el final del comentario. Por ejemplo, son válidos los siguientes comentarios: (**) (* hola *) (*ho** la, que *hay *) (* ho)la )***) b) Comentarios de java: Comentario de línea, Comentario de varias líneas y comentario de documentación

5

Ejercicio 5 Sea el alfabeto ∑ = {a, _} . Obtener una expresión regular que denote el lenguaje de todas las palabras que cumplen las siguientes dos condiciones: 1. El número de símbolos a es par (posiblemente 0). 2. No pueden tener dos o más símbolos _ de forma consecutiva. Palabras válidas: ε , aa , _ , _a_a , aaa_a_aa_ Palabras no válidas: a , __ , a__a , a_aa Ejercicio 6 Dado el alfabeto ∑ = {a, b}, sean los siguientes lenguajes: L1 = {an | n >= 0} y L2 = {bm | m > 0 } Se pide: Encontrar una expresión regular lo más simplificada posible que defina los siguientes lenguajes:

L+1 ⋅ L*2 , L1 , ∑* − L1 , L 2 ∩ L1 , ( L1 ⋅ L 2 ) * − {wb | w ∈ {a, b}* } Ejercicio 7 Sea el lenguaje L1 definido sobre un alfabeto Σ={a,b} y formado por las palabras que no contienen la subpalabra ab y un lenguaje L2 definido sobre igual alfabeto y formado por las palabras que no contienen ni aa ni ab. Se pide: Determinar las expresiones regulares simplificadas que denoten cada uno de los siguientes lenguajes: L1, L2, L1∩ L2, L1- L2 Ejercicio 8 Con ∑={a,b}, sea L1 el lenguaje formado por las palabras que no finalizan en ab y L2 el de las palabras que no acaban en ba. Ejemplos L1: ε, b, a, bba, abb, aaaaabb Ejemplos L2: ε, aa, b, bab, bbbbb Se pide: Indicar las expresiones regulares, lo más simplificadas posible, para los siguientes lenguajes: a) L1, L1 | L2, L1 - L2, L1 ∩ L2, ∑*- L1 Sea L1 un lenguaje definido sobre un alfabeto Σ ={a,b} formado por las palabras que tienen un número impar de símbolos a y como máximo dos símbolos b consecutivos. Ejemplos válidos: a, aaba, aaabbaba, babbabbab Ejemplos no válidos: ε, aabbba, bb, abbabbaba Sea L2 un lenguaje definido sobre un alfabeto Σ ={a,b} formado por las palabras que tienen un número par de símbolos a (el 0 se considera un número par) y como máximo dos símbolos b consecutivos. Ejemplos válidos: ε, aa, aaaba, aaabbaaba, baabbabbab, bb Ejemplos no válidos: a, aabbbaa, aabbabbaba Se pide 1. Encontrar una expresión regular que denote el lenguaje L1. 2. Justificar si se cumplen o no las siguientes igualdades: a) L1 | L2=Σ* b) L1.L2=L2.L1 c) L1*=Σ* d) L1=L2 complementario

6

3.3 Autómatas Los autómatas tratan de simular cualquier proceso de nuestra vida cotidiana, en este caso van simular el proceso de la información, proceso de las palabras de un lenguaje. En el campo de los Procesadores de Lenguajes, los lenguajes tratados están formados por palabras definidas sobre un alfabeto, palabras que no son otra cosa que una secuenciación de símbolos. En el caso de los Procesadores de Lenguajes, los autómatas hacen de reconocedores de lenguajes, reciben en su entrada una cadena de símbolos y decide a la salida si dicha palabra pertenece al lenguaje Un autómata es una máquina abstracta reconocedora de lenguajes formales, que acepta o reconoce las palabras que componen un lenguaje formal El autómata recibe la secuencia de símbolos de la entrada los procesa y va produciendo una salida. En este proceso es importante saber la situación en que se encuentra y los posibles estados por los que pasa el autómata en momento determinado, y así, poder decidir sobre la salida. Definición conceptual Conceptualmente un autómata es un modelo que simula una relación de tres componentes: - Una entrada, sobre la que se representa y simula la palabra a reconocer - Una memoria, que permite y posibilita el reconocimiento de palabras con estructuras complejas - Un control, mecanismo que determina como evoluciona el autómata en función: del símbolo leído de la entrada, el símbolo obtenido de la memoria auxiliar y el estado donde está situado || -----

a a

b

-

-

---Control de estados

Estado

δ

Estado(s Función de transición

------

A A

B

-

-----

El diseño del control crea lo que denominamos evoluciona el estado (situación) del autómata

función de transición, que determina como

Situaciones en un autómata Situación de un autómata - Estado en el que se encuentra un autómata en un momento dado (estado actual, subpalabra que falta por reconocer, situación memoria); (qactual , b.., B.. ) Situación inicial - Estado inicial o de partida de un autómata (estado inicial, palabra a reconocer, situación inicial memoria); (qinicial , x=aab., #) Situación de aceptación (o de reconocimiento) - Estado de aceptación (o de reconocimiento) de un autómata (estado de aceptación, palabra reconocida, situación final memoria); (qfinal, ε, α ) Movimiento en un autómata - es el paso de una situación a otra. O lo que es lo mismo la aplicación de una transición a una situación del autómata. Situación actual del autómata - (qm, x=abb$, A…#), Transición posible - (qm, a, A)→(qn, B) Aplicando la transición a la anterior situación, queda (qn, bb$, B…#) nueva situación – se ha pasado al estado qn, se ha leído a de la entrada y se ha sustituido B por A en la memoria.

7

Lenguaje reconocido por un autómata Conjunto de palabras que partiendo del un situación inicial se llega a una situación final en cero o más movimientos . (qi , x. #) - representa una situación de inicio ( x palabra a reconocer, # inicio memoria ) (qf, ε, α ) - representa una situación de reconocimiento (ε se ha leído la palabra) (qi, x=aab, #)→ ( )→…. (qf, ε, α ), x es una palabra reconocida Lenguaje reconocido por un autómata es el conjunto de palabras que partiendo de una situación inicial se llega a una situación de aceptación en cero o más movimientos. L (A)={x∈Σ* | (qi. x. #) →* (qf, ε, α ) , x es una palabra reconocida} Tipos de Autómatas, atendiendo a los movimientos que se pueden dar en una situación: Deterministas: para cualquier situación existe como máximo un movimiento. En decir en una situación sólo puede darse como máximo una transición, siguiente ejemplo. ∀ (qi, a, A ) → (qj, B) a ∈ Σ ; qi, qj ∈ Q ; A, B ∈ Γ (alfabeto de la memoria) (qi, aab, A.. ) → (qj, ab, B… ), No deterministas: existe alguna situación que tiene más de un movimiento. Es decir existen situaciones en las cuales se pueden dar más de una transición, siguiente ejemplo: ∃ (qi, a, A ) →{ (qj, AA.. ) (qk, AB..)…} La situación (qi, aab, A ) → (qj, ab, AA… ), tiene más de un movimiento (qi, aab, A ) → (qj, ab, AA… ), la anterior situación tiene más de un movimiento (qi, aab, A ) → (qk, ab, AB …) Tipos de autómatas, atendiendo al lenguaje que reconocen: - Autómata finito (regular) – reconocen los lenguajes regulares (lenguajes de tipo 3) - Autómata de pila – reconocen los lenguajes independientes del contexto (tipo 2) - Autómata acotados linealmente – reconocen los lenguajes dependientes del contexto (tipo 1) - Máquinas de Turíng – reconocedor universal (tipo 0)

3.4 Autómatas Finitos (AF) Es un modelo que simula una máquina abstracta que acepta (o reconoce) las palabras de un lenguaje regular. En el caso de los AF el mecanismo de control de evolución no necesita de memoria (los estados del propio autómata hacen de memoria) debido a la simplicidad de la estructura de las palabras de los lenguajes regulares a reconocer || -----

-

a

a

b

-

---Control de estados

Estado

δ

estados Función de transición

Las palabras de este tipo de lenguajes no tienen una estructura equilibrada, es decir la historia de una parte de la palabra no afecta a la otra parte. Solo es necesario el par relacionado (estado, entrada), donde el estado se relaciona con una entrada, en la cual sólo se permite leer y avanzar símbolo a símbolo.

8

Situación de un AF: es un par ordenado de la forma (qi, ax) donde: qi es el estado actual del AF, a es el símbolo señalado para leer y, x es la cadena que resta por leer en ese momento Situación inicial: ( q0, ax); q0 estado inicial, a es el símbolo señalado para leer y, x es la cadena que resta por leer en ese momento, ax es cadena de entrada a reconocer por el AF Situación final o de aceptación: ( qf, ε) ; qf es el estado final, ε la cadena ha sido aceptada, se ha llegado a leer toda la palabra y terminamos en un estado de aceptación Movimiento: es el paso de un estado a otro, (qi, x) → (qj, y) ⇔ ∃ (qi, a) → (qj) Sea x=ay , a∈ Σ ⇒ (qi, x=aab) → (qj, ab) Tipos de AF atendiendo a los movimientos que se pueden dar en una situación: AF determinista – Cualquier situación tiene como máximo un movimiento ∀ (qi, a) → (qj) , a∈ Σ qi, qj∈Q ⇒ (qi, abb) → (qj, bb) AF no determinista – Existe alguna situación que tiene más de un movimiento, dos casos: - Sin transiciones vacías AFND ∃ (qi, a) → {qj, qk,…}, a ∈ Σ , qi, qj, qk ∈Q (qi, abb) → (qj , bb) (qi, abb) → (qk, bb) - Con transiciones vacías AFND_ ε ∃ (qi, ε) → (qj), a∈ Σ , qi, qj ∈Q (qi, abb) → {(qj, abb), (qj, abb)}

3.4.1.- Definición formal AFD Es aquel que ante una determinada entrada sólo se puede transitar a un estado Un AFD se define mediante una quíntupla AF=(Σ, Q, δ, q0, F), donde: - Σ : alfabeto de las palabras a reconocer por el autómata - Q: conjunto de estados, es un conjunto finito no vacío - δ: Q x Σ → Q, función de transición, que transforma el par ordenado (qi, a) → qj - q0 ∈ Q, estado inicial (estado de partida) - F ⊆ Q: conjunto no vacío de estados finales o de aceptación Dado el siguiente lenguaje L = {anbm | n, m>0}, especificar un AFD que lo reconozca: AF= (Σ={a, b}, Q={ q0, q1, q2}, δ, q0, F={ q2}), δ: (q0, a) → {q1} (q1, b) → {q2} (q1, a) → {q1} (q2, b) → {q2} Representación gráfica de los AF Para mejorar la legibilidad y visibilidad de los autómatas se pueden utilizar dos tipos de representaciones gráficas: los diagramas de transición o las tablas de transición: Diagramas de transición La representación por medio diagrama de transiciones, es un grafo dirigido, en el que: - Los nodos que se representan por un circulo, que se etiquetan con los estados q∈Q - Habrá arcos etiquetados con a desde el nodo qi al qj, si existe la función δ(qi,a)→qj - El estado inicial tiene un arco entrante no etiquetado → - Los estados finales qf ∈ F se señalan por doble circulo Ejemplo de un AFD representado por un diagrama de transición, que reconoce el lenguaje : L = {anbm | n,m>0} a q0

a

b q1

b

q

fig1

9

Tablas de transición Representación tabular que relaciona dos componentes: entradas y estados - Cada fila corresponde a un estado q∈Q - Cada columna corresponde a un símbolo de entrada a∈ Σ - La fila asociada al estado inicial tiene una → - Las filas asociadas a los estados finales tienen el símbolo * En la posición (q, a), q ∈ Q y a∈ Σ está el estado que determine la función δ(q, a) AFD representado por una tabla de transición que reconoce el lenguaje L = {anbm | n,m>0} entradas estados

a

b

→q0 q1 *q2

q1 q1 --

-q2 q2

- Lenguaje reconocido por un autómata finito determinista Conjunto de palabras que partiendo del una situación inicial, se llega a un estado final en cero o más movimientos. Movimiento en un AFD: es el paso de un estado a otro. (qi, x) → (qj, y) ⇔ ∃ (qi,a) → (qj) ; x=ay , a∈ Σ Ejemplo fig 1: (q0, abb)→(q1,bb)→….→(q2,ε)

(qi, x=aab) → (qj, ab)

Lenguaje={ x |x ∈Σ*, (qi , x)→*(qf,ε), qf ∈F } AFD

3.4.2.- Definición formal AFND Los AFND es una extensión de los AFD que tiene la capacidad de transitar a más de un estado para una misma entrada. Un AFND se define mediante una quíntupla AF=(Σ , Q, δ, q0, F), donde: - Σ : alfabeto de las palabras de lenguaje a reconocer - Q : conjunto de estados, es un conjunto finito no vacío, - δ: Q x Σ → P(Q), representa subconjunto de estados de Q. Función de transición, que transforma el par ordenado (qi, a)→{qj,..} - q0 ∈ Q, estado inicial - F ⊆ Q: conjunto no vacío de estados finales o de aceptación Dado el siguiente lenguaje L = {anbm | n,m>0}, especificar un AF que lo reconozca: AF=(Σ={a,b}, Q={ q0, q1, q2}, δ, q0, F={ q2}), δ : (q0, a) → {q0} (q1, b) → {q1}

(q0, a) → {q1} ⇒ (q0, a) → {q0, q1} (q1, b) → {q2} ⇒ (q1, b) → { q1,q2}

Diagramas de transición - Los nodos que se representan por un círculo, que se etiquetan con los estados q∈Q - Habrá arcos etiquetados con a desde el nodo qi a los nodos qj, qk,.. si existe δ(qi, a)→qj, δ(qi, a)→qk,…⇒ δ(qi,a)→{qj, qk,..} - El estado inicial tiene un arco entrante no etiquetado → - Los estados finales qf∈F se señalan por doble circulo AFND representado por un diagrama de transición que reconoce el lenguaje L = {anbm | n,m>0} a

b q0

a

q1

b

q fig2

10

Tablas de transición - Cada fila corresponde a un estado q∈Q - Cada columna corresponde a un símbolo de entrada a∈ Σ - La fila asociada al estado inicial tiene una → - Las filas asociadas a los estados finales tienen el símbolo * - En la posición (q,a) q∈Q y a∈ Σ están los estados que determine δ(q,a) AFND representado por una tabla de transición que reconoce el lenguaje L = {anbm | n,m>0} Entradas estados

a

b

→q0 q1 *q2

{q0, q1} q1 --

-{q2 q1} --

- Lenguaje reconocido por un autómata finito no determinista Conjunto de palabras que partiendo del una situación inicial, se llega a un estado final en cero o más movimientos. Un AFND acepta una cadena x si es posible elegir una secuencia de opciones de estados partiendo de uno inicial y finalizar por uno de aceptación Movimiento: es el paso de un estado a otro. (qi, x) → { (qj, y), (qk, y) } ⇔ ∃ (qi, a) → {qj, qk} x=ay , a∈ Σ (qi, x=aab) → (qj, ab) → (qk, ab) Ejemplo fig 2:

(q0, abb)→(q0, bb)→….(q2, ε) →(q1, bb)→….(q2, ε)

Lenguaje={x | x ∈ Σ*, (qi , x)→*(qf, ε) ∩ F≠Φ} AFND Otra representación del lenguaje generado por un AFND L(A)={ x | x ∈ Σ*, δ*(qi , x) ∩ F≠Φ} δ*(qi. x) contiene al menos un estado de aceptación

3.4.3. - Definición formal AFND-ε Una extensión de los AF que permite transiciones vacías. Las transiciones vacías hacen que se pueda realizar un movimiento sin lectura de la entrada. Un AFND_ε se definen mediante una quíntupla AF=(Σ , Q, δ, q0, F), donde: - Σ : alfabeto de las palabras a reconocer - Q : conjunto de estados, es un conjunto finito no vacío, - δ : Q x {Σ ∪ε}→ P(Q) función de transición, que transforma el par (qi,ε)→{qj,..} P(Q), representa subconjunto de estados de Q, función de transición - q0 ∈ Q, estado inicial - F ⊆ Q: conjunto de estados finales o de aceptación Dado el siguiente lenguaje L = {anbm | n,m>0}, especificar un AFND-ε que lo reconozca: AFND-ε = (Σ={a,b}, Q={ q0, q1, q2, q3}, δ, q0, F={ q3}) δ: (q0, a) → {q1} (q2, b) → {q3} (q1, a) → {q1} (q3, b) → {q3} (q1, ε) → {q2} Diagramas de transición - Los nodos se etiquetan con los estados q∈Q - Habrá arcos etiquetados con ε desde el nodo qi al qj, qk,.. si existe δ(qi,ε)→qj qk.. - El estado inicial tiene un arco entrante no etiquetado → - Los estados finales qf∈F se señalan por doble círculo

11

AFND- ε representado por un diagrama de transición que acepta el lenguaje L= {an bm | n, m>0} a q0

a

q1

b q2

ε

b

q fig3

Tablas de transición - Cada fila corresponde a un estado q∈ Q - Cada columna corresponde a un símbolo de entrada a ∈ Σ ∪ ε - La fila asociada al estado inicial tiene una → - Las filas asociadas a los estados finales tienen el símbolo * - En la posición (q, a) q∈Q y a∈ Σ∪ε está el estado(s) que determine δ (q, a) o δ (q, ε) AFND-ε representado por una tabla de transición que reconoce el lenguaje L = {anbm | n, m>0} Entradas estados →q0 q1 q2 *q3

a

b

ε

q1 q1 ---

--q2 q3

-q1,q2 ---

- Lenguaje reconocido por un autómata finito no determinista con transiciones vacías Conjunto de palabras que partiendo del una situación inicial, se llega a un estado final en cero o más movimientos. Movimiento: es el paso de una situación a otra. (qi, x) → (qj, x) ⇔ ∃ (qi, ε) → (qj) x =a y , a∈ {Σ∪ ε} (qi, x=aab)) → (qj, aab) → (qj, aab) Ejemplo fig3:

(q0, aabb)→(q1, abb)→ q1, bb) →….(q2,ε) →(q2, abb)→…..

Lenguaje={ x |x ∈Σ*, (qi.x)→*(qf, ε) ∩ F≠Φ} AFND- ε Otra representación del lenguaje generado por un AFND- ε Lenguaje={ x |x ∈Σ*, δ*(qi. x) ∩ F≠Φ} Los AFND-ε facilitan la programación del AFND, están estrechamente relacionados con ER

3.5 Autómatas equivalentes Dos o más autómatas A1, A2,.., son equivalentes A1≈ A2 ≈.. si aceptan el mismo lenguaje, es decir L(A1)=L(A2)=…los autómatas vistos en los apartados anteriores de la figura (1,2,3) son equivalentes. Los AF ya sean deterministas o no deterministas tienen la misma potencia de reconocimiento de lenguajes, en el sentido que cualquier lenguaje regular puede se reconocido por un AF ya sea determinista o no determinista con o sin transiciones vacías. Desde el punto de vista práctico, es conveniente que el autómata sea determinista el proceso es directo más simple de implantar y más rápido, pero desde el punto de vista teórico son interesante los no deterministas porque permiten modelizar el algoritmo de búsqueda y retroceso, también son importantes y de gran utilidad los AFND con transiciones vacías sobre la teoría de lenguajes formales

12

3.6 Autómatas completos Se dice que un autómata finito es completo cuando para todos los estados se dan todas las transiciones. ∀ a∈ Σ , ∀ qi, qj ∈ Q ∃ (qi, a) → (qj) | (qi, abb) → (qj, bb) Cualquier autómata finito no completo puede hacerse completo, poniendo un estado de error o estado trampa, al cual transitan todas las transiciones no permitidas en el reconocimiento del lenguaje Dado el siguiente lenguaje L = {anbm | n, m>0}, especificar un AFD completo que lo reconozca: AF=(Σ={a,b}, Q={ q0, q1, q2}, δ, q0, F={ q2}), (q0, a) → {q1} (q0, b) → {qerror} (q1, b) → {q2} (q1, a) → {q1} (q2, a) → {qerror} (q2, b) → {q2} a q0

a

b q1

b

b

q a

qer

a,b

fig 4 Los autómatas finitos completos son interesantes desde el punto de vista, de la obtención de su complementario, basta con cambiar estados finales por no finales y viceversa, para obtener el AF que reconoce su lenguaje complementario. El siguiente AFD reconoce el lenguaje complementario al lenguaje que reconoce el anterior autómata.

a q

a

b q

b

b

q2 a

qe

a,b

fig 5

3.7 Autómata conexo Un autómata finito es conexo cuando desde el estado inicial en cero o más movimientos se llega a todos los estados. qi (estado inicial) (qi, x) →* (qj) ∀ qj ∈ Q todos los AF visto hasta hora son conexos Convertir un AF dado en otro equivalente que sea conexo, consiste en quitarle los estados inaccesibles a q0

a

b q

b

b

a q

⇒

a q0

q

a qe

b qe

a,b

fig 6

a,b

13

3. 8 Simulación de un AFD El fin de un AF es el del reconocimiento de un lenguaje. A continuación se describen dos formas de simular la implementación de los autómatas finitos - simulación por medio del diagrama de transiciones Posicionarse en el estado inicial qi Leer el primer carácter de la entrada a Mientras ( no sea fin de la entrada) hacer Moverse a un estado dependiendo de la entrada y estado actual qi,a →qj Leer el siguiente carácter b Si el estado es final entonces palabra reconocida qi∈F Sino error la palabra no es reconocida. “error” - situación por medio de la tabla de transiciones Posicionarse en el estado inicial qi Repetir Leer el primer carácter de la entrada a Obtener siguiente estado [ estado actual, entrada leída] [qi,a]=qj Hasta estado final o error La representación en forma de tabla tiene la ventaja de un rápido acceso, su desventajas son que necesitan bastante memoria cuando el alfabeto de entrada es grande y, existen muchas transiciones vacías, también tiene una estructura estática para cualquier modificación es más costosa. Las representaciones mediante listas es mas compacta pero es más lenta en su proceso. Implementar la función como un segmento de código con estructuras CASE dentro del programa que simula el proceso de reconocimiento de las palabras es más eficiente.

3.9 Equivalencia entre AFN y AFD Transformación de AFND en AFD Un lenguaje L que puede ser reconocido por un AFND, puede encontrarse un AFD equivalente que reconozca el mismo lenguaje. Un AFD es un caso particular de un AFND, puesto que (qi, a) → |(qj)| =1, a∈Σ , ∀ |qj|∈Q En un AFND ∃ (qi, a) → |(qj, qk,…)| ≥1, a∈Σ, qi, qj, qk∈Q Para evitar el no determinismo hay que unir todos los estados a los que se llega con una misma entrada (qi, a) →{qj, qk,…}, los estados (qj, qk,…), se llega con la entrada a, que formarán un estado del AFD Mueve(qi, a)={qj, qk,..}=Ai los estados que forman Ai mantiene las relaciones de transición con el resto de los estados. Ai a

q1

….. a

a q0

q2 b

……⇒

…. q3

q2

….. ……

q0 b

….

q3

…… fig.5

Mueve(qo, a)={q1, q2,..}=Ai

Transformación de AFND- ε en AFD Dado un AFND puede considerarse un caso restringido de un AFND-ε, δ(qi, ε) = φ ∀ qi∈Q . Un lenguaje reconocido por un AFND puede ser reconocido por un AFND-ε equivalente.

14

∃ δ(qi, ε) = {qj, qk,..}, estados {qi, qj, qk,..} se puede llegar sin leer nada de la entrada, es decir se pueden agrupar en un estado del AFD para evitar el no determinismo Se utiliza la operación cierre, para agrupar todos los estados. Cierre-ε (q) estados alcanzables desde el estado q, a través de transiciones vacías. Cierre- ε (q)= { p | δ(q, ε) →* δ(p, ε) , q∈Q }

ε a q0

q1

……

q2

………

ε b

q0,

b

a

q2

….

q3

…….

a q3

fig.6

Cualquier lenguaje regular (tipo 3) puede ser reconocido por un autómata finito. Sin embargo un AFD puede dar lugar a reconocedores más rápidos y más fácil de realizar debido a que solo existe un camino; mientras que en los AFN hay que realizar un backtracking buscando todos los posibles caminos. Transformación de AFN en AFD- método de los subconjuntos Se trata de agrupar estados del AFN para evitar el no determinismo producido por las condiciones vista anteriormente Un AFN se caracteriza por cumplir algunas de las siguientes condiciones: - Existen estados que ante una determinada entrada aєΣ van a más de un estado{qi, qj …}, estados que se pueden agrupar (AFND) (qi, a) → {qi, qj …}=Ai - Existen transiciones vacías, todos los estados unidos por transiciones vacías se pueden agrupar

(AFND- ε) (qi, ε ) → (qi, qj ); (qj, ε ) → (qk, ql ) => { qi, qj ,qk, ql}=Ai Ejemplo de AFN: b a

a

q1

q3

b

q5

ε

q0

a

q2

ε

q4

q7

ε

q6

b fig.7

Obtención del AFD, aplicando las condiciones anteriores, por medio de agrupaciones de estados: - Estado inicial será el conjunto de estados alcanzables a través de transiciones vacías del estado inicial del AFND Cierre_ ε (q0)={q0,…}=A0

A0 es un estado no tratado del AFD

Un estado Ai es no tratado cuando no se han comprobado las entradas para los estados del AFND que lo componen. - Mientras que existan estados no tratados hacer: Elegir un estado no tratado Ai y ∀ a є Σ hacer: Mov (Ai,a)={}=Aj {estados alcanzables desde los estados del AFND que forman Ai y la entrada a}

15

Cierre_ε (Aj)= Ak {estados que se pueden sumar a los anteriores al estar unidos por transiciones vacías} Se obtiene un estado Ak, que de no estar tratado lo incluiremos en el conjunto de los no tratados Cálculo del ejemplo anterior: entradas Estados AFD

a

b

A0

{q0}

{q1, q2 ,q4, q6}=A1

-----

A1

{q1, q2 ,q4,q q6}

-----

{q0, q3,q7}=A2

A2

{ q0, q3, q7}

{q1, q2 ,q4, q6, q5}=A3

-----

A3

{q1, q2 ,q4, q6, q5}

-----

{ q0, q3, q7}=A2

Construcción del AFD buscado: - El estado inicial del AFD será aquel que contenga el estado inicial del AFND - Todos los estados Ai del AFD mantienen las entradas que tienen los estados del AFND - Los estados finales del AFD serán aquellos que contengan algún estado final del AFND a

A

A

b

A

b a

A

fig.8

El AFD obtenido no es mínimo, mínimo sería el siguiente: A

b a

A

fig.9

Tanto el autómata de la figura 7, como el de la figura 8 y 9 son equivalentes, reconocen el lenguaje denotado por la ER => (ab)* Transformación de AFD a AFD mínimo – creando clases de equivalencia: Se trata de agrupar estados que tienen el mismo comportamiento. (estados que tienen las mismas funciones) Dos o más estados {qi, qj,.. }tienen el mismo comportamiento, cuando esos estados para las mismas entradas ∀ aєΣ transitan a los mismos estados (qi, a) → {qk} (qj, a) → {qk}

(qi, b) → {ql} (qj, b) → {ql}

{qi, qj} tienen el mismo comportamiento

a a

q1 q3

q0 b

…. q2

⇒

q0

a,b

a

q1

q2

a fig. 10

(q1, a) → {q3} ; (q2, a) → {q3}

⇒ (q12, a) → {q3}

Los estados finales y no finales tienen distinto comportamiento, unos por ser reconocedores y los otros no. a

q1

a q3

q0 b

…. q2

⇒

q0

a,b

q1

a

q2

a fig 11

16

⇒ (q12, a) → {q3}

(q1final, a) → {q3} ; (q2no final, a) → {q3} Obtención del AFD mínimo:

- Se crea una partición inicial del conjunto de estados en dos grupos: finales y no finales P0 : G0={estados no finales} G1={estados finales} - Por cada grupo de comportamiento de una partición hacer: Dos o más estados pertenecientes al mismo grupo, seguirán en el mismo grupo si tienen el mismo comportamiento (Gi, a)→Gn ; (Gi, b)→Gm ; Gi se mantiene como un grupo En otro caso el grupo se divide en tantos subgrupos como comportamiento distintos existan (Gi, a)→Gn, Gm ⇒ Gi=Gi1, Gi2 ;

Gi se divide en dos subgrupos

- El proceso anterior se repetirá hasta que no se creen más subgrupos en las particiones que se van obteniendo Construcción del AFD buscado: - El estado inicial del AFD mínimo será aquel grupo que contenga el estado inicial del AFD - Todos los grupos obtenidos en la última partición serán estados del AFD mínimo, estados que mantienen las entradas de los estados del AFD de partida - Los estados finales del AFD mínimo serán aquellos grupos formados por estados finales del AFD de partida a) Haciendo el AFD completo: a,b qe

b q0

a

a

b b

q1

a q2

b a

fig. 12

q3

El estado de error qe forma parte del grupo de los no finales P0 => G0 = {q1, q3, qe} G0 q1 q3 qe

a G0 G0 G0

G1 = {q0, q2 }

b G1 G1 G0

(* partición cero *) G1 q0 q2

P1 => G0 = {q1, q3], G1 = {qe}, G2 = {q0, q2 } G0 q1 q3

a G1 G1

b G2 G2

G2 q0 q2

a G0 G0

a G0 G0

b G0 G0

(* partición uno *) b G1 G1

G1 qe

a G1

b G1

Construcción del AFD buscado: - El estado inicial del AFD mínimo será aquel grupo que contenga el estado inicial del AFD - Todos los grupos obtenidos en la última partición serán estados del AFD mínimo, estados que mantienen las entradas de los estados del AFD de partida - Los estados finales del AFD mínimo serán aquellos grupos formados por estados finales del AFD de partida

17

G

a,b

b AFD mínimo obtenido

a b a

G

fig.13

G

b) AFD no completo – obtención del AFD mínimo a través de un AFD no completo b a b q 1 q0 q3 q2 a fig. 14

P0 => G0 = {q1, q3 } G0 q1 q3

a -----

G1 = {q0, q2 }

b G1 G1

´---` representa un grupo no definido G1 q0 q2 G

AFD mínimo obtenido

a G0 G0

b -----

b a

G

fig. 15

- Equivalencia entre AF y gramáticas de tipo 3 Por tratarse de dos mecanismos regulares que permiten especificar lenguajes regulares, se puede establecer una transformación de uno al otro, nada mas que cambiando de forma de representación. - Se trata de adaptar la representación del AF a la gramática de Tipo 3 de la siguiente forma: A=(Σ, Q, δ, q0, F) => G=(Σ, N, S, P) - A cada estado del AF se le hace corresponder un elemento no terminal de la gramática - Al estado inicial le corresponde el símbolo inicial - Las transiciones se transforman en producciones de la siguiente forma: (qi, a) → {qj}

Ai→aAj

Ai,AjєN

qi↔Ai ; qj↔Aj

∀ qf є F (qi, ε) → {qj}

Af→ε Ai→Aj

AfєN Ai,AjєN

qf↔Af qi↔Ai ; qj↔Aj

Ai→Aj es una producción que no corresponde a las gramáticas de tipo 3, para evitarla sustituimos a Aj por las partes derechas de producciones donde Aj figure como parte izquierda

q0

a

b q1

b

ε q2

a fig.16

Ejemplo : A=( Σ={a, b},Q={q0, q1, q2}, δ, q0, F={q2}) Δ: (q0, a) → {q1} , (q1, ε) → {q2} , (q1, b) → {q1} , (q2, a) → {q2} , (q2, b) → {q1} G = (Σ={a,b},N={A0,A1,A2}, A0,P) P : A0→aA1 , A1→A2|bA1 , A2→bA1|aA2|ε A0→aA1 , A1→ bA1|aA2|ε , A2→bA1|aA2|ε Equivalencia entre gramáticas de tipo 3 en AF Proceso es inverso al apartado anterior en donde ahora conocemos la representación de la gramática y hay que obtener la del AF

18

G=(Σ, N, S, P) => A=(Σ, Q, δ, q0,F) - A cada elemento no terminal de la gramática se le hace corresponder un estado del AF - Al símbolo inicial le corresponde el estado inicial - Las producciones se transforman en transiciones de la siguiente forma: Ai→aAj (qi, a) → {qj} Ai, AjєN qi↔Ai ; qj↔Aj Para las producciones Ai→a se crea un único estado final qf al que se llega desde el estado qi y la entrada a Ai→a (qi, a) → {qf} qf є F Para cada una de las producciones Ai→ ε se pone el estado qi asociado a Ai como final Ai→ ε qiєF qi↔Ai Ejemplo : G= (Σ={a, b}, N={ A0, A1, A2 }, A0, P) P : { A0→aA1 , A1→ bA1| aA2| b| ε , A2→bA1| aA2| a |ε } A= ( Σ={a,b}, Q={ q0, q1, q2, qf}, δ, q0, F={q1, q2, qf }) Δ : (q0, a) → {q1} , (q1, a) → {q2} , (q1, b) → {q1} , (q1, b) → {qf} , (q2, a) → {q2} , (q2, b) → {q1}, (q2, a) → {qf} qt

b

b a

q0

q1

a a

a

q2

fig.18

b Equivalencia entre AFD y ER Para conocer este tipo de equivalencias hay que plantear el AFD como un sistema de ecuaciones. La forma de plantear el sistema de ecuaciones es similar al propuesto de pasar de AF a gramática de tipo 3, con las siguientes diferencias en su representación: - La flecha separadora de las producciones se sustituye por el símbolo = - La barra de alternativa | se sustituye por un + - Los elementos no terminales se renombran por x para adecuarlo a la representación de un sistema de ecuaciones a q0

Ejemplo:

fig.19 AFD => G A0→aA0 |ε => x0 = ax0 + ε

x0= ax0 + ε ; x0 representa una expresión regular (ER) que denota el lenguaje a reconocer desde q0 o a generar desde A0 Aplicando la regla de inferencia de ER ω = α* β = α ω | β o lo que denominamos ecuación característica (o fundamental) x = A* B = Ax + B x0=ax0+ε => aplicando e.c. a*.ε=a* b Ejemplo: q0

a

q1

a b

q2

a

fig.20

A0 → aA1 A1 → bA1 | a A2 A2 → bA1 | aA2 | ε

19

Planteándolo como un sistema de ecuaciones: x0 = ax1 x1 = ax2+bx1 x2 = ax2+bx1+ε aplicando e.c. x2 = a*.( bx1+ε ) y sustituyendo en la 2ª ecuación: x1 = a (a*.(bx1+ε) )+bx1 = a (a*bx1+a*) + bx1= a+bx1+a++bx1 = (a+b+b)x1+ a += (a+b+b)*.a+ sustituyendo el valor de x1 en la 1ª ecuación x0=a ( (a+b+b)*. a+) = a ( (a+b|b)*. a+ )= a ( a+b |b )*.a+ ⇒ a ( a |b )*. a Las ER obtenidas por medio de ésta transformación no están simplicadas. Transformación de ER en AFND – método de thompson - Es una transformación dirigida por la sintaxis, de forma que usa la estructura sintáctica de la ER para guiar y representar el proceso de construcción del AFN. Se basa en las siguientes reglas : La ER ε es equivalente al AF siguiente

ε

q0

q1

a

La ER a es equivalente al AF siguiente q0

q1

La ER α | β es equivalente al AF que reconoce el lenguaje denotado por la ER α alternativa con el AF que reconoce el lenguaje denotado por la ER β. En definitiva ambos mecanismos definen el lenguaje L(α) |L(β) ε

q1

AF(α)( )

ε

q2

q0

q5 q3

ε

AF(β)( )

q4

ε

La ER α. β es equivalente al AF que reconoce el lenguaje denotado por la ER α concatenado con el AF que reconoce el lenguaje denotado por la ER β: En definitiva ambos mecanismos definen el lenguaje L(α) . L(β)

q0

AF(α)( )

q1

ε

q2

AF(β)( )

q3

*

La ER α es equivalente al AF que reconoce L(α)*. En definitiva ambos mecanismos definen el lenguajeL(α)* ε ε q1

q0

AF(α)( )

ε q2

q3

ε

La ER α+ es equivalente al AF que reconoce L(α)+. En definitiva ambos mecanismos definen el lenguaje L(α)+

20

ε

q1

AF(α)( )

q2

Ejemplo - transformación de la ER a.(b|c*)* en el AFN siguiente : a

ε AF(b|c*) AF (b|c*)* ε

ε

ε

AF(b|c*) AF (b|c*) ε ε

AF (b)

ε

AF (c*) ε

ε c

ε

b

ε ε

ε

Ejercicios 1- Construir un AFD para cada uno de los siguientes lenguajes formales: a) Dado el alfabeto Σ={1,2,3}, sea el lenguaje L={w∈{1,2,3}+ | la suma de las cifras de w es múltiplo de 4 }. Por ejemplo, serían válidas 13, 31, 2222, etc. b) Sea el lenguaje L= {w∈{0, 1}* | en w, la subcadena “00” aparece como mucho dos veces }. Por ejemplo, la palabra 000 pertenece al lenguaje por tener dos subcadenas “00”, pero no la palabra “0000”, ya que contiene tres subcadenas “00”. Otros ejemplos de palabras válidas son: 01001001, 01000, 1011. Ejemplos de palabras NO correctas: 0100100100, 01000100, 010000. c) Dado el alfabeto ∑ = {0, 1}, sea el lenguaje de todas las palabras que, tienen un número impar de símbolos 1, y además contienen la subcadena 01. Por ejemplo, serían válidas las subcadenas 01, 010101, 110111. Pero no lo serían 1, ε, 011 ó 0101. d) Σ={a,b,c,d}. Las palabras que pertenecen a este lenguaje cumplen las condiciones de que si aparece la subpalabra db siempre está seguida por el símbolo c, y si aparece la subpalabra ba siempre está seguida por el símbolo d. Por ejemplo, las siguientes palabras: a, dbcb, aabccbadc. e) Σ={a, b, c}. Pertenecen a este lenguaje las palabras que tienen un número par de veces (posiblemente ninguna) la subcadena bc. f) Σ={a, b}. Las palabras tienen un número par de símbolos a y no contienen la subpalabra bbb (se considera que el 0 es un número par).

21

2) Los comentarios en el lenguaje de programación Pascal se escriben de la siguiente manera: •

Comienzan por los símbolos (* y terminan por *).

•

Si llamamos símbolo a cualquier carácter ASCII menos ‘*’ y ‘)’, en el interior del comentario se puede escribir cualquier cantidad de símbolos, incluyendo ninguno. Pero además, dentro del comentario se pueden usar los caracteres ‘*’ y ‘)’ siempre y cuando no haya un ‘*’ seguido de un ‘)’, en cuyo caso se interpretaría como el final del comentario. Por ejemplo, son válidos los siguientes comentarios: (**) , (* hola *), (*ho** la, que *hay *), (* ho)la )***)

Se pide: Construir un AFD que reconozca los comentarios de Pascal.En dicho AFD se utilizará símbolo para representar a cualquier carácter menos ‘*’ y ‘)’ 3) Sea el alfabeto ∑ = {a, _} . Obtener un AFD mínimo que reconozca el lenguaje de todas las palabras que cumplen las siguientes dos condiciones: El número de símbolos a es par (posiblemente 0). No pueden tener dos o más símbolos _ de forma consecutiva. Palabras válidas: ε , aa , _ , _a_a , aaa_a_aa_ Palabras no válidas: a , __ , a__a , a_aa 5- Dado el siguiente AFD definido sobre el alfabeto Σ={a,b} que reconoce el lenguaje L, formado por las palabras que contienen al menos una vez la subpalabra aa:

q0

b a b

a, b q1

a

q2

Modificarlo, obteniendo un AFD que reconozca el lenguaje L ∪ {a}.

6 - Dado el alfabeto ∑ = {a,b} y, sean los lenguajes L1 y L2 definidos respectivamente mediante los siguientes AFD

L1

L2

q0

b a b

b

b a a

q0

q1

q1

Se pide: a) Una ER para el complementario de L1 b) Un AFD para L1 – {b} c) Una ER para L2 d) Un AFD para L22. e) Una ER para Σ*- L1* 6- El autómata siguiente reconoce el lenguaje L. q1

0

1 0

q0

q2

0

1 Se pide: a) Expresión regular simplificada que reconozca L. b) Expresión regular simplificada que reconozca el lenguaje complementario de L. c) Encontrar un autómata finito determinista mínimo que reconozca L*.

22