TLP - Poblemas Tema 2 - Escuela Técnica Superior de Ingeniería de Sistemas Informáticos PDF

Preview

Summary

Escuela Técnica Superior de Ingeniería de Sistemas Informáticos...

Description

Tema 2 LENGUAJES REGULARES. LÉXICO Ejercicio 1 Construir un autómata finito que reconozca el lenguaje L = { x | x no tiene 3 ceros consecutivos } definido sobre el alfabeto {0,1}.

SOLUCIÓN: El autómata finito puede ser el siguiente: 0,1 0

0

0

q1

q0 0

q2

1

1

1 q4

1

q3

20

LENGUAJES REGULARES. LÉXICO

Ejercicio 2 Diseñar un AFD capaz de reconocer las palabras del alfabeto {a} que tengan un número de a´s múltiplo de 4.

SOLUCIÓN:

a q1

a

q2

a

q0

a

q3

Ejercicio 3 Construir un AFD que reconozca el lenguaje de las palabras que contienen n símbolos a y m símbolos b en cualquier orden, cumpliendo |n - m| mod 4 = 0.

SOLUCIÓN: Este lenguaje es el de las palabras formadas por a´s y b´s, y que cumplan que la diferencia entre el número de a´s y de b´s que hay en la palabra sea múltiplo de 4. Por ejemplo la palabra bbbabb pertenecería al lenguaje ya que hay cinco b´s y una a, y cinco menos uno es cuatro, que es múltiplo de cuatro. El autómata sería el siguiente: a q1

a q0

b

a b

q2

b a

b q3

21

LENGUAJES REGULARES. LÉXICO

Ejercicio 4 (junio 1994) El funcionamiento del editor de textos vi, puede describirse (parcial y simplificadamente) mediante las siguientes normas: • El editor tiene 3 modos de funcionamiento: - Modo Comando. - Modo Inserción. - Modo Sustitución. • Al entrar en el editor el modo de funcionamiento es el Modo Comando. • En el Modo Comando todos los caracteres que se teclean se interpretan como comandos del editor: - Si se teclean los comandos: 'a','i','o', se pasa al Modo Inserción. - Si se teclean los comandos: 's','w','c', se pasa al Modo Sustitución. - Para suprimir texto, sin alterar el modo de funcionamiento, se aceptan los comandos: 'x','d'. • En el Modo Inserción se insertan en el texto los caracteres que se teclean. • En el Modo Sustitución se sustituye parte del texto por los caracteres que se teclean. • Siempre que se pulsa la tecla se pasa al Modo Comando. Se pide: Constrúyase un autómata regular determinista que represente el funcionamiento (aquí descrito) del editor vi. Deberá especificarse claramente: 1. El alfabeto de entrada. 2. El conjunto de estados (indicando lo que cada uno de ellos representa). 3. Las transiciones.

SOLUCIÓN: El autómata finito determinista que describe el funcionamiento del editor vi es el siguiente: letra x,d,ESC

I

a,i,o C

ESC s,w,c ESC

S

letra En este autómata, letra se interpreta como cualquier símbolo de la ´a´ a la ´z´. ESC representa la tecla .

22

LENGUAJES REGULARES. LÉXICO

El alfabeto de entrada es el formado por los símbolos de la ´a´ a la ´z´, y por el símbolo ESC. Los estados del autómata son C,S, e I. El estado C corresponde al modo comando, y es el estado inicial, el estado S corresponde al modo sustitución y por último el estado I corresponde al modo inserción. Las transiciones entre dichos estados se han indicado implícitamente en el diagrama de transiciones. Se ha supuesto que al terminar de editar se regresa al estado C, definiéndose por ello este estado como final.

Ejercicio 5 (septiembre 1996) Para el alfabeto {a,b} construir un AFD completo mínimo (con 7 estados) que reconozca las palabras con un número par de a's y que no contienen la subpalabra 'bbb'. Se considera que el 0 es un número par. En caso de obtener un autómata de 7 estados no es necesario comprobar que sea mínimo.

SOLUCIÓN: El autómata finito determinista mínimo, con 7 estados, sería : a,b b

q0

b

q1

b

q2

a a a a

a

q3

a

b q4

b q5

b

q6

23

LENGUAJES REGULARES. LÉXICO

Ejercicio 6 (septiembre 1996) Dados los siguientes lenguajes sobre el alfabeto {a,b}: • L1 = palabras que empiezan y finalizan por símbolos diferentes • L2 = palabras que tienen los dos últimos símbolos iguales Construir un AFD que reconozca el lenguaje L1 U L2.

SOLUCIÓN: El autómata finito determinista que reconoce la unión de ambos lenguajes sería: a

q2

a

b b

a

b

q3

q1

a

q0

b b

q4

q6

a b

a

a q5

b

Ejercicio 7 Dado el alfabeto {0,1} indicar si son regulares los siguientes lenguajes: 1. El conjunto vacío. 2. La palabra vacía. 3. Las palabras de longitud una. 4. Todas las palabras posibles. 5. Las palabras de longitud d (d>=0). 6. Las palabras con tres símbolos '0'. 7. Las palabras con igual número de símbolos '0' que de símbolos '1'. 8. Las palabras de longitud menor o igual que d (d>=0).

24

LENGUAJES REGULARES. LÉXICO

SOLUCIÓN: Lenguaje 1 El conjunto vacío, se puede denotar mediante un mecanismo regular, en concreto con Æ, lo que significa que es regular. Lenguaje 2 La palabra vacía sí es un lenguaje regular, ya que se reconoce con un autómata finito de un único estado, siendo dicho estado final. Se podría denotar con e. Lenguaje 3 Las palabras de longitud una, son un lenguaje regular, pues con 0|1, que es una expresión regular, se puede denotar dicho lenguaje. Lenguaje 4 El lenguaje de todas las palabras posibles también es regular, pues con (0|1)*, que es una expresión regular, se puede denotar este lenguaje. Lenguaje 5 Analizamos ahora las palabras de cualquier longitud: • Las palabras de longitud 0, es decir la palabra vacía, es un lenguaje regular. • Las palabras de longitud 1, como hemos indicado antes, también es un lenguaje regular. • Las palabras de longitud 2, se pueden denotar con (0|1)(0|1), expresión regular que indica que el lenguaje es regular. • Las palabras de longitud 3, se podrían denotar con (0|1)(0|1)(0|1), y las palabras de mayor longitud se denotarían de la misma manera con expresiones regulares. • Las palabras de cualquier longitud, por tanto, definen un lenguaje regular. Lenguaje 6 Las palabras con tres símbolos 0 también definen un lenguaje regular, pues con 1*01*01*01*, que es una expresión regular, denotamos dicho lenguaje. Lenguaje 7 El lenguaje de las palabras con igual número de símbolos 0 que símbolos 1, no es regular, porque es imposible definir un mecanismo regular, que reconozca o genere las palabras con igual número de 0´s y de 1´s, si este número es un número cualquiera. Sí sería posible construir un autómata finito que reconociera las palabras con igual número de 0´s y de 1´s, si este número fuera uno determinado.

25

LENGUAJES REGULARES. LÉXICO

Lenguaje 8 Las palabras de longitud menor o igual que una determinada, definen un lenguaje que es regular: • Las palabras de longitud igual que 0, son solamente la palabra vacía, que definía un lenguaje regular. • Las palabras de longitud menor o igual que 1, o sea las palabras de longitud 0 ó 1, también definía un lenguaje regular. • Las palabras de longitud menor o igual que 2, o sea las palabras de longitud 0 ó 1 ó 2, también definía un lenguaje regular. Las palabras de longitud menor o igual que una determinada, razonando como se ha hecho hasta ahora, definen un lenguaje regular.

Ejercicio 8 Dado el siguiente diagrama de transición de un autómata finito, indicar cuál es el lenguaje reconocido por dicho autómata, denotándolo con una expresión regular, y transformar el autómata en una gramática de tipo 3.

b

q0

a,b

q1

a

q2

a

SOLUCIÓN: El lenguaje reconocido por el autómata es (a|b)ab*(aab*)*. Este lenguaje se puede generar con la gramática de tipo 3: A -> aB | bB B -> aC | a C -> bC | b | aB

26

LENGUAJES REGULARES. LÉXICO

Ejercicio 9 (septiembre 1994) L es un lenguaje formal, que reconoce las siguientes cuatro clases de palabras, sobre el alfabeto {0,1}: 1. Palabras que tienen al principio un número indeterminado de símbolos 0 finalizando por un 1, seguido de un número indeterminado de símbolos 1, finalizados por el par 01. 2. Palabras que alternativamente tiene un 0 y un 1 y finalizan por 0. 3. Palabras de longitud impar, comenzando por un 0. 4. Palabras que tienen en cabecera un número indeterminado de símbolos 0, seguidos o no por un 1, finalizados por una secuencia indeterminada de símbolos. Nota: Indeterminado se entiende como cero o más ¿Es L un lenguaje regular? Si L es regular, representar su expresión regular?

SOLUCIÓN Sí es un lenguaje regular, ya que se puede representar mediante la expresión regular: 0*11*01 | (01)*0 | 0(00|01|10|11)* | 0*(1|e)(0|1)*

= (0|1)*.

Ejercicio 10 (febrero 1995) Dadas las siguiente gramáticas: 1. S -> abA | bbB A -> bC B -> a C -> cS C -> e 2. D -> 0F | e F -> 0F | 1G | 0 G -> 1G | 1 Indicar la expresión regular que define cada uno de los lenguajes. Describir las propiedades de las palabras definidas por cada una de las gramáticas.

SOLUCIÓN: Gramática 1 El lenguaje de esta gramática es el siguiente: S => abA => abbC => abb S => abA => abbC => abbcS => abbcabA => abbcabbC => abbcabb S => abA => abbC => abbcS => abbcabA => abbcabbC => abbcabbcS => => abbcabbcabA => abbcabbcabbC => abbcabbcabb

LENGUAJES REGULARES. LÉXICO

27

De donde deducimos que genera el lenguaje de las palabras que terminan por abb o bba precedidas de la palabra vacía o de la palabra abbc, la cual se puede repetir un número cualquiera de veces. En notación matemática sería el lenguaje L = { (abbc)n abb | n³0 } È { (abbc)n bba | n³0 }. La expresión regular asociada es: (abbc)*( bba | abb ) Gramática 2 D -> 0F | e F -> 0F | 1G | 0 G -> 1G | 1 Esta gramática genera las siguientes palabras: D => e D => 0F => 00 D => 0F => 00F => 000 D => 0F => 01G => 011 D => 0F => 01G => 011G => 0111 En definitiva produce la palabra vacía, o las palabras compuestas por dos o más 0´s. Genera también las palabras que comienzan por 0´s, seguidos por dos o más 1´s. La expresión regular correspondiente es: e | 00*0 | 00*111*

Ejercicio 11 (febrero 1996) Dados dos lenguajes regulares L1 y L2, razonar las siguientes afirmaciones: 1. L1 · L2 es regular. 2. L1 U L2 es regular. 3. El lenguaje complementario de L2 es regular.

SOLUCIÓN: Apartado 1 L1 · L2 es regular, ya que si L1 es regular, se puede denotar con la expresión regular ER1, y L2 , por la misma razón, con la expresión regular ER2 . Con estas dos expresiones se puede formar una nueva expresión regular ER3, definida como ER3= ER1· ER2, la cual por construcción es regular. ER3 denota un lenguaje regular, el lenguaje L3, que coincide con L1 · L2 . Por lo tanto L1 · L2 es regular.

28

LENGUAJES REGULARES. LÉXICO

Apartado 2 L1 U L2 es regular, porque si L1 y L2 son regulares, se pueden denotar con las expresiones regulares ER1, y ER2 respectivamente. Empleando estas dos expresiones se puede formar una nueva expresión regular ER3, definida como ER3= ER1 | ER2, que por construcción es regular. ER3 denota un lenguaje regular, el lenguaje L3, que coincide con L1 U L2 . Por lo tanto L1U L2 es regular. Apartado 3 El lenguaje complementario de L1 es regular, puesto que si L1 es regular se puede reconocer dicho lenguaje con un autómata finito. Transformando dicho autómata en uno completo, y redefiniendo los estados finales como no finales y viceversa, obtenemos otro autómata que reconoce el lenguaje complementario del que reconocía el autómata inicial. Del autómata transformado, mediante un algoritmo, se puede obtener una expresión regular que denote el lenguaje complementario. Este lenguaje por tanto, es regular. Por lo tanto el lenguaje complementario de L1 es regular.

Ejercicio 12 (Septiembre 1996) Dado el alfabeto {a,b,c} construir una expresión regular para el siguiente lenguaje formal: palabras que finalizan en 'c' y que no contienen la subpalabra 'aa'. Demostrar que la palabra bac queda denotada en dicha expresión regular.

SOLUCIÓN: La expresión regular sería: (b|c|ab|ac)*(c|ac) Dicha expresión representa las palabras que terminan en c, y que no contienen la subpalabra aa, ya que cualquier ocurrencia del símbolo a se da al lado de una ocurrencia de un símbolo b o c, pero nunca de otra a. La palabra bac se denota en esta expresión regular, seleccionando b de (b|c|ab|ac)* y ac de (c|ac).

29

LENGUAJES REGULARES. LÉXICO

Ejercicio 13 (Septiembre 95) Dados los siguientes lenguajes: L1 = {wÎ{0,1}*| en w cada aparición de un 0 va inmediatamente precedida y seguida de un 1} L2 = {wÎ{0,1}*| w=X101Y donde X no acaba en 10 e YÎ{0101}*} Se pide: 1. Dibujar los autómatas finitos, deterministas o no pero sin transiciones para la cadena vacía, que reconozcan cada lenguaje, razonando el desarrollo realizado. 2. Crear la expresión regular que define cada uno de los lenguajes, justificando incrementalmente cada una de las subexpresiones componentes.

SOLUCIÓN: Apartado 1 El autómata finito correspondiente a L1 es el siguiente: 1 1

1

q0

q2

q1

0 El autómata finito correspondiente al lenguaje L2 es: 0 1 q0

0

q5

q4

q3

1

0

1

1

0

1 q1

0

q2

1

q6

q8

0

1 1 q7

30

LENGUAJES REGULARES. LÉXICO

Para construir este autómata, se creó previamente el que reconoce las palabras que no terminan en 10 : 0

q0

1

0 1 q1

0

q2

1 Apartado 2 • La expresión regular de L1 es e | 11* (011*)*. • La expresión regular de L2 es

( e | (0|1)*1 | (0|1)*00 | 0 ) · 101 · (0101)*.

La parte ( e | (0|1)*1 | (0|1)*00 | 0 ) corresponde a las subpalabras que no terminan en 10.

Ejercicio 14 (junio 1995) Dada la siguiente gramática G=({a,b},{,,},,P), con P: ::= b ::= a b ::= b | b | b ::= | Se pide: 1. Indicar el tipo de la gramática propuesta , razonanado la respuesta. Definir el lenguaje generado por la misma a través de una expresión regular.

2. Construir una gramática de tipo tres equivalente.

31

LENGUAJES REGULARES. LÉXICO

SOLUCIÓN: Apartado 1 La gramática es de tipo 1, ya que hay producciones cuya parte izquierda tiene más de un símbolo, y en estas producciones la longitud de esta parte izquierda es siempre menor o igual que la longitud de la parte derecha. El lenguaje generado por esta gramática sería el denotado por la expresión regular aa*ba*a. Apartado 2 La gramática de tipo 3 que genera el mismo lenguaje sería: A -> aB B -> aB | bC C -> aC | a

Ejercicio 15 Construir una expresión regular y un AFD para los identificadores del lenguaje C. Estos identificadores comienzan por una letra y pueden continuar por letras, dígitos o el carácter de subrayado. Restringiendo la longitud de los identificadores a no más de 4 símbolos, construir la expresión regular y el autómata finito determinista correspondiente.

SOLUCIÓN: La expresión regular de los identificadores, sin restricción alguna, sería ésta : (A|B|...|Z)(A|B|...|Z|0|1|2|3|4|5|6|7|8|9|_)* Por simplificar, se ha utilizado (A|B|...|Z), que se interpreta como: la letra A, la letra B, las letras que están comprendidas entre la B y la Z, y la letra Z. Se han empleado sólo las letras mayúsculas, y no las minúsculas, ya que con éstas la expresión regular sería similar pero menos legible. El autómata finito determinista correspondiente sería: A,B,...,Z,0,...,9,_ A,B,...,Z q0

q1

La expresión regular, con la restricción de la longitud no mayor de 4, sería:

32

LENGUAJES REGULARES. LÉXICO

(A|B|...|Z) · (A|B|...|Z|0|...|9|_|e) · (A|B|...|Z|0|...|9|_|e ) · (A|B|...|Z|0|...|9|_|e) El autómata finito determinista correspondiente a los identificadores de longitud 1, 2, 3 ó 4 sería: A,B,...,Z q0

A,B,...,Z,0,...,9,-

A,B,...,Z,0,...,9,q1

q2

q3

A,B,...,Z,0,...,9,-

q4

Ejercicio 16 Las constantes de tipo carácter en el lenguaje de programación C pueden responder a las siguientes tres estructuras: Un carácter alfanumérico cualquiera entre comillas simples. Ejemplo: 'k','2'. Existen también ciertos caracteres no imprimibles que se representan mediante secuencias de escape: '\n' (nueva línea), '\t' (tabulador), etc. Siendo, por tanto, su descripción léxica '\l', donde l es un carácter alfabético cualquiera. Además, cualquier carácter arbitrario se puede especificar de la forma '\ddd', donde ddd puede tener de 1 a 3 dígitos octales. Por ejemplo, '\137' se corresponde con el carácter cuyo valor ASCII es el 137 en octal. Se pide: 1. Encontrar una expresión regular, y una gramática de tipo 3, que especifiquen dichas constantes. 2. Definir un autómata finito determinista que reconozca dichas constantes. 3. Implementar en el lenguaje de programación Pascal, un subprograma para el reconocimiento de las constantes carácter con el formato ´\l´, siendo l un carácter alfabético cualquiera.

SOLUCIÓN Apartado 1 La expresión regular que denota este lenguaje sería: ´(a|...|z|0|...|9)´ | ´\ (a|...|z)´ | ´\ (0|...|7) (e|0|...|7) (e|0|...|7)´ La gramática que genera este lenguaje sería: A -> ´B

33

LENGUAJES REGULARES. LÉXICO

B -> aC |...| zC | 0C |...| 9C | \E C -> ´ E -> aC | ... | zC | 0F | ... | 7F F -> ´ | 0G | ... | 7G G -> ´| 0H | ... | 7H H -> ´ Apartado 2 El autómata que reconoce dichas constantes es éste:

q0

a,...,z 0,...,9

´ q1

q3

´

q4

a,...,z

\ q2

0,...,7

0,...,7 q5

0,...,7

q6

q7

´

´

´

q8

Apartado 3 El subprograma para el reconocimiento de las constantes carácter con formato ´\l´, en el lenguaje de programación Pascal es: PROCEDURE reconocer_constante; (* procedimiento que reconoce las constantes del formato especificado *) VAR estado:integer; (* estado del autómata *) estado_definido:boolean; (* estado que ha sido previamente definido *) simbolo: char; (* símbolo de la palabra *) fichero: text; (* fichero donde está almacenada la palabra a reconocer *) BEGIN assign(fichero,”fichero”); reset(fichero); estado:=0; estado_definido:=true; WHILE not eof(fichero) and estado_definido DO

34

LENGUAJES REGULARES. LÉXICO

BEGIN read(fichero, simbolo); CASE estado OF 0:CASE simbolo OF ´ ´ ´:estado:=1; ELSE estado_definido:=false; END:; 1: CASE simbolo OF ´ \ ´:estado:=2; ELSE estado_definido:=false; END; 2: CASE simbolo of ´a´..´z´:estado:=3; ELSE estado_definido:=false; END; 3: CASE simbolo OF ´ ´ ´:estado:=4; ELSE estado_definido:=false; END; 4: CASE simbolo of ´ ´ ´,´\´,´a´..´z´: estado_definido:=false; END; END; END; IF estado=4 AND estado_definido THEN write(´reconocida constante´) ELSE write(´palabra no reconocida´); close(fichero); END;

35

LENGUAJES REGULARES. LÉXICO

Ejercicio 17 Escribir el autómata finito y la gramática que definen un lenguaje capaz de representar los números sin signo del lenguaje de programación L, los cuales pueden ser : cero, decimal y octal. Siendo un número decimal el que no comienza por cero y octal el que comienza por cero.

SOLUCIÓN: El autómata finito sería el siguiente: 0,1,..,9

q1

1,..,9 0 q0