| 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 21-30

> 21.- Escribir la gramática que defina un lenguaje capaz de representar a los números sin signo del lenguaje PILOT, los cuales pueden ser: cero, decimal y octal. Siendo un número decimal el que no comienza por cero y octal el que comienza con cero.

> Con las tres tipos <Cero>, <Decimal> 'y <Octal>, la gramática:

> <Número> → <Cero> | <Decimal> | <Octal>
> <Cero> → 0
> <Decimal> → <Dig.-0-dec'> | <Decimal> <Dígito>

> <Octal> → <Cero> <Dig.Octal> | <Octal> <Dig.- Octal>
> <Dig. -0- dec> → 1| 2 | 3|4|5|6|7|8|9
> <Dígito> → <Cero> | <Dig.-0-dec>

> 22.- Dado un autómata como el siguiente, representarlo como máquina de Moore con salidas asociadas a cada estado. Como máquina de Mealy con salidas a cada arco de transición.

> 23.- Dado el lenguaje am bn c dp para m, n > 0, p => 0. Definir el autómata correspondiente y la expresión regular.

> El siguiente autómata es el que representa a este lenguaje:

> 24.- Dibujar el diagrama de transiciones para la expresión regular siguiente:

> b a* c a + a b* c b

> 25.- Dar el diagrama de transiciones, las reglas BNF y la expresión regular de la gramática definida por:

> A cn b + b cn a para n = > 0

> 26.- Dar el diagrama de transiciones, las reglas BNF y la expresión regular de la gramática definida por:

> (ab + bc) (b + c)*

> las reglas son:

> S → aA B → c
> S → bB lab → b
> A → b lab lab → c lab
> A → b lab → b lab
> B → c lab lab → Cc

> 27.- Diseñar un autómata que analice el formato de la sentencia format de FORTRAN en lo que respecta al número de paréntesis, que no se aceptan en una profundidad de 2. Que acepte como correctos:

> (2F10.3)
> (‘FIN1’,3(218))
> ( )

> En cambio, como incorrectos, los siguientes:

> 8(F6.3)
> 813
> ((213,6(18)))

> Se incluye la matriz de transición y el diagrama de estados

> 28.- Se pide definir completamente el autómata que reconozca las sentencias de declaración explicita de FORTRAN como la siguiente:

> REAL A,B (5,8,J),C,D

> Suponiendo que no se limita el número de dimensiones y que algunos de los estados son:

> Tomar el nombre de una variable.
> Abrir paréntesis.
> Tomar una constante como dimensión.
> Separar con una coma dos dimensiones.
> Tomar una variable como dimensión.
> Cerrar paréntesis.
> Separar con coma dos variables.

> Además de los estados indicados, tenemos el inicial O y uno de error E.
> Primeramente se da en la Fig. C.9 a) la matriz de transición que luego en b)
> ·se completa con el estado de error E.

> Los estados 1 y 6 son finales.

> 29.- Escribir el autómata programable que reconozca el lenguaje 0n 1n para n => 0. Dibujar el diagrama gráfico de estados. Modificar el diagrama anterior para que se excluya el caso de n = 0.

> Se trata de reconocer las sentencias del lenguaje L = {0n 1n | n = > 0} con
> un autómata de pila. La idea consiste en apilar los ceros en la pila y al llegar
> los unos se va emparejando cada uno con el cero superior de la pila, que
> se suprime. Si al final la pila esta vacía coincidirán el número de ceros con
> el de unos. Sea y la función de transición 8 vale:

> a) δ (q0,0,Z0) (ql,0Z0)
> b) δ (ql , 0, 0) = (ql, 00)
> c) δ (ql , 1, 0) = (q2, λ) .
> d) δ(q2,1,0) = (q2, λ)
> e) δ (q2, δ, Z0) (q0 , λ)

> en la figura siguiente se incluye el diagrama gráfico de este AP. Para su mejor
> seguimiento se señala cada uno de los cinco valores anteriores de δ con
> su letra (a - e) dentro de un círculo en el arco correspondiente.

> 30.- Construir un traductor finito que reconozca expresiones aritméticas de:

> S → + S | - S | a + S | a – S | a

> Y quite los operándoos unarios redundantes, como por ejemplo:

> ( - a + - a - + -a. –a –a + a)

> El Traductor finito es el de la figura siguiente que es un autómata finito que lleva en cada arco, después de una barra, la salida correspondiente.

> Para el caso propuesto:

> 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