| INSTITUTO POLITÉCNICO NACIONAL ESCUELA SUPERIOR DE CÓMPUTO |

Introducción | Contenido | Bibliografía

Introducción
Contenido
UNIDAD I
UNIDAD II
UNIDAD III
UNIDAD IV
UNIDAD V
UNIDAD VI
UNIDAD VII
UNIDAD VIII
UNIDAD IX
PROBLEMARIO Problema Unidad 8.4 Problemas 1-10 Problemas 11-20 Problemas 21-30

Problemas 31-40

Problemas 41-50

Bibliografía

PROBLEMARIO

Problemas 31-40

> 31.- Construir un autómata que reconozca la sentencia “GO TO nnnn”, pudiendo tener varios espacios o ninguno entre las letras.

> El diagrama de estados es el de la figura siguiente. Se aceptan blancos antes del
> GOTO, entre las letras y antes del número de línea.

> 32.- Seguir los estados recorridos en el análisis lexicográfico de las siguientes constantes reales, con los autómatas siguientes, indicando si son correctas o no:

> La siguiente tabla es la solución:

> 33.- Escribir un programa de hashing y el almacenamiento correspondiente para manejar un autómata con Hash. Cada elemento es de la forma (x, y, valor) para los elementos o estados no nulos.

> En Pascal la declaración de los datos sería como sigue:

> const
> tamtab = 17; { Tamaño de la tabla HASH }
> type
> elemento = record { Para elementos no nulos del autómata}

> x, y integer; { Coordenadas del elemento }

> valor: integer; { Coordenadas del elemento}

> end;
> var
> TABLA: array [l..tamtab] of elemento;. { Hash}

> La función de hash tendrá en cuenta las dos coordenadas de cada elemento:

> function hash (x, y : integer): integer;
> var
> clave : integer;
> begin
> clave := 100 * y + x;
> hash := (clave mod tamtab) + 1
> end

> empleando las funciones VER y ADD similares a las descritas en el texto,
> se puede llenar la tabla con los elementos o tercetos no nulos. Luego el
> acceso de un elemento se hará con "TABLA[k]. valor" determinando
> previamente k no nulo con la función VER.

> 34.- Escribir un explorador completo, es decir su diagrama de transición, gramática regular, diagrama de estados y sus acciones semánticas para la metanoción <Numero sin signo> del ALGOL 60, que según el informe revisado se tiene:

> <Número sin signo> ::= <Numero decimal>
> <Número sin signo> ::= <Parte exponente>
> <Número sin signo> ::= <Numero decimal> <Parte exponente>

> Estas reglas no son todas del tipo 3, para lo que deben ser como se sabe del fomato A::= aB o bien def A: := b. Después de convertirlas a formato 3, queda la gramática regular siguiente:

> <Número sin signo> ::= “digito" <Resto de número sin signo>
> <Número sin signo> ::= . <Fracción decimal>
> <Número sin signo> ::= E <Parte exponente>
> <Resto número sin signo> ::= "digito" <Resto número sin signo>
> <Resto número sin signo> ::= . <Fracción decimal>
> <Resto número sin signo> ::= E <Parte exponente>
> <Resto número sin signo> ::= λ
> <Fracción decimal> ::= "digito" <Resto fracción decimal>
> <Resto fracción decimal> ::= λ
> <Resto fracción decimal> ::= E <Parte exponente>
> <Resto fracción decimal> ::= “digito" <Resto fracción decimal>
> <Parte exponente> ::= "signo" <Entero exponente>
> <Parte exponente> ::= "digito" <Parte entero exponente>
> <Entero exponente> ::= "dígito" <Resto entero exponente>
> <Resto entero exponente> ::= "dígito" <Resto entero exponente>
> <Resto entero exponente> ::= λ

> Observemos que hay dos reglas con la parte derecha nula o lambda. Ahora
> todas las reglas son del tipo 3; conviene notar que algunas reglas llevan un
> terminal subrayado: "signo" o "dígito" que representan un conjunto de
> caracteres, el primero los diez dígitos y el segundo los dos signos posibles
> más y menos. Es decir que cada regla donde aparecen estos símbolos subrayados
> es una abreviatura de 10 ó 2 reglas respectivamente.

> En la Fig. C.13 se ve el diagrama de estados del mismo autómata de reconocimiento.
> Se señala con una flecha el estado inicial del autómata, y con un doble círculo los estados finales del autómata. No se han incluido los estados de error.
> Se aprecia la similitud de esta figura con el autómata del problema 32, si bien ésta es algo más complicada. También aquí se han indicado los nombres de las metanociones
> de la gramática regular. Con la numeración de estados elegida, la matriz
> de transición y de acciones semánticas es idéntica a la del problema 32.

> 35.- En el lenguaje BASIC, suponer que los identificadores sólo pueden ser o bien una letra o una letra seguida por un dígito. En este caso escribir un autómata que reconozca la sentencia IF, como la siguiente:

> IF A > B1 THEN 1010

> Que valga también para el caso en que se suprimen todos los blancos intermedios. Compárese con el caso en que los identificadores pueden ser de mayor longitud.

> Si el blanco fuera separador, se tomaría cada identificador y a posteriori
> se examinaría si es del lenguaje (IF, THEN, ELSE, LET, etc.) o no. Si el
> blanco no es separador entonces se tendría para reconocer la sentencia
> condicional el diagrama de la figura siguiente (se ha simplificado a una relación
> con dos variables de dos caracteres cada una y separadas por un operador
> de relación de sólo un carácter).

> 36.- Escribir las reglas BNF de la gramática de un lenguaje regular que represente la estructura de un bloque, como el siguiente:

> begin D1; D2; … Dn;
> S1; S2; … Sm
> end

> siendo Di las declaraciones de las variables y Sk las sentencias.

> Si suponemos las declaraciones y sentencias ya reconocidas y abreviadas
> con los tokens "d" y "s" respectivamente (tamb'ién son tokens begin y
> end) se tiene la solución de la Fig. C.l s.

> 37.- Escribir las acciones semánticas para la máquina automática de accionamiento por monedas.

> Si se emplean las variables globales.

> IMPORTE para saber el dinero introducido,
> COSTE es el coste de los productos seleccionados,
> PROD, PROE, PROF número de los productos respectivos seleccionados;

> algunas de las acciones semánticas son
> A : IMPORTE:= IMPORTE + 5;
> D : PROD:= PROD + 1;
> SAL : COSTE:= PROD*20 + PROE*80 + PROF*140;
> if IMPORTE >= COSTE then
> (* Emitir las cantidades de productos PROD, PROE y PROF
> y el sobrante IMPORTE - COSTE *)
> else begin
> (* Mensaje de error *)
> (* Devolver IMPORTE *)
> End

> 38.- Escribir la gramática y luego el programa para KPM que reconozca el lenguaje dado por la expresión regular bb* c.

> La gramática sería:

> S' → S$
> S → Bc
> B → b | bB

> y el programa KPM sería similar al del texto.

> 39.- Escribir la gramática y luego el programa para KPM que reconozca el lenguaje dado por la expresión regular b(c + d) (c + d)* ee.

> La gramática en forma standard es
> S' → S$
> S → bAee
> A → c | d | B | dA
> B → cA

> y el programa KPM sería:

> 40.- Escribir un programa KPM para reconocer sentencias del lenguaje de la gramática:

> S → A | (S)
> A → B > B
> B → b | c | d | (B * B)

> Aplicar a la sentencia (b * c) > c, o bien a la misma escrita entre paréntesis.

> Un ejemplo similar a éste es el que desarrolla Knuth. La gramática ya está en forma standard.

> El programa KPM es:

> que aplicándolo a la sentencia (b * c) > c $ dará la traza siguiente;

> Luego la sentencia “(b * c) > c $” es correcta

> Atrás Siguiente

##### Introducción / Contenido / Unidad I / Unidad II / Unidad III / Unidad IV / Unidad V / Unidad VI / Unidad VII / Unidad VIII / Unidad IX / Problemario / Bibliografía

##### Inicio

##### Créditos

José Sánchez Juárez, Andrés Ortigoza Campos, Fabiola Ocampo Botello