Siguiente: Autómatas finitos y expresiones Un nivel arriba: Gramáticas formales Anterior: Ejercicios

Programas

1. Considere la regla de transformación MAI visto en la sección 1.2.1:

Si $\sigma_0\in \mbox{\it MAI\/}^*$, el árbol de derivación de $\sigma_0$ es el árbol (tal vez infinito, pero tal que cada nodo posee un conjunto finito de hijos) $\mbox{\it Ar\/}_{\mbox{\scriptsize\it MAI}}(\sigma_0)$ cuyos nodos están etiquetados por palabras en $\mbox{\it MAI\/}^*$ y cuyas aristas lo están por las producciones I, II., III. o IV. definido recursivamente como sigue:

1.

La raíz de $\mbox{\it Ar\/}_{\mbox{\scriptsize\it MAI}}(\sigma_0)$ tiene como etiqueta a $\sigma_0$.

2.

Para cada nodo de $\mbox{\it Ar\/}_{\mbox{\scriptsize\it MAI}}(\sigma_0)$, digamos que etiquetado con la palabra $\sigma$, si no se le puede aplicar ninguna producción a $\sigma$ entonces este nodo se declara como hoja, en otro caso,

(a)

pongamos un contador de hijos h igual a 0, y apliquemos, en tanto sea posible, las reglas siguientes en el orden en que las presentamos:

(b)

si $\sigma$ termina con i, $\sigma=\sigma_1i$, hacemos h:=h+1 y le añadimos un h-ésimo hijo a $\sigma$ etiquetándolo con $\sigma_1ia$, y a la arista que los une con I.,

(c)

si $\sigma$ comienza con m, $\sigma=m\sigma_1$, hacemos h:=h+1 y le añadimos un h-ésimo hijo a $\sigma$ etiquetándolo con $m\sigma_1\sigma_1$, y a la arista que los une con II.,

(d)

si $\sigma$ contiene la cadena iii, para cada vez que aparezca esa cadena, es decir siempre que podamos escribir $\sigma=\sigma_1iii\tau_1$, hacemos h:=h+1 y le añadimos un h-ésimo hijo a $\sigma$ etiquetándolo con $\sigma_1a\tau_1$, y a la arista que los une con III.,

(e)

si $\sigma$ contiene la cadena aa, para cada vez que aparezca esa cadena, es decir siempre que podamos escribir $\sigma=\sigma_1aa\tau_1$, hacemos h:=h+1 y le añadimos un h-ésimo hijo a $\sigma$ etiquetándolo con $\sigma_1\tau_1$, y a la arista que los une con IV.

Escriba un programa que reciba una cadena $\sigma_0\in \mbox{\it MAI\/}^*$ y un número natural n y enliste los n primeros nodos de $\mbox{\it Ar\/}_{\mbox{\scriptsize\it MAI}}(\sigma_0)$ en un recorrido ``a lo ancho'' (si no los hubiere ha de indicar que éste es el caso).

2. Considere la gramática del recuadro siguiente:

El árbol de derivación de S es el árbol (tal vez infinito, pero tal que cada nodo posee un conjunto finito de hijos) $\mbox{\it Ar\/}_{G}$ cuyos nodos están etiquetados por palabras en (S+A+B+0+1)^* y cuyas aristas lo están por las producciones I, II., III., IV., V., VI. definido recursivamente como sigue:

1.

La raíz de $\mbox{\it Ar\/}_{G}$ tiene como etiqueta a S.

2.

Para cada nodo de $\mbox{\it Ar\/}_{G}$, digamos que etiquetado con la palabra $\sigma$, si $\sigma\in (0+1)^*$ entonces este nodo se declara como hoja, en otro caso, se aplica la producción que corresponda, examinando $\sigma$ por la izquierda y las producciones en el orden enlistado.

Escriba un programa que partiendo del símbolo inicial S y un número natural n, enliste los n primeros nodos de $\mbox{\it Ar\/}_{G}$ en un recorrido ``a lo ancho'' (si no los hubiere ha de indicar que éste es el caso). Decida si el lenguaje de esta gramática es o no vacío.

3. Siguiendo la idea del algoritmo de Markov mostrado en la sección 1.2.3, diseñe un algoritmo de Markov para multiplicar por el entero 5 números enteros en binario. Escriba un programa que reciba como entrada la representación en base 2 de un entero n y muestre visualmente la aplicación sobre él del algoritmo que lo ``quintuplica''.

4. Enumeración con representación en octetos: Utilice la representación en base 256=2⁸ de los números enteros. Cada dígito en tal representación es un byte. Un arreglo de k bytes $\mbox{\bf a}=[a_{k-1},a_{k-2},\ldots,a_{1},a_{0}]$, $0\leq a_i\leq 255$ representa al número

$$m_{\mbox{\scriptsize\bf a}}=a_{k-1} 256^{k-1} + a_{k-2} 256^{k-2} + \cdots + a_{1} 256^{1} + a_{0}.$$

Imprima a cada dígito a_i como una pareja de dígitos hexadecimales: $00=0,\ldots,FF=255$ Para un alfabeto $\Sigma$ de m caracteres considere la enumeración $c:\Sigma^*\to I\!\!N$ definida en la Proposición 2.2.4. Escriba sendos programas para los problemas siguientes:

1.

Dada m y una cadena $\sigma\in\Sigma^*$, calcule $c(\sigma)$ y lo exprese representado en octetos.

2.

Dada m y un número entero x representado en octetos, calcule $\sigma\in\Sigma^*$ tal que $x=c(\sigma)$.

5. Sea $A=\{a_1,\ldots, a_n\}$ un conjunto de n elementos. Para cada relación binaria $R\subset A\times A$, consideremos la matriz $M_R=\left(m_{ij}\right)_{i,j\leq n}\in \{0,1\}^{n\times n}$, llamada de adyacencia, tal que

$$\forall i,j\leq n:\ m_{ij}=\left\{\begin{array}{ll} 1 &\mbox... ...a_j)$, } \\ 0 &\mbox{\rm en otro caso. } \end{array}\right.$$

Escriba un programa que dados $n\in I\!\!N$ y una matriz $M\in \{0,1\}^{n\times n}$ decida (de manera efectiva y eficiente) si la relación R cuya matriz de adyacencia es M es:

1.

reflexiva,

2.

simétrica,

3.

antisimétrica,

4.

transitiva,

5.

de equivalencia,

6.

de orden.

De la evidencia que dé este programa, conjeture cuántas relaciones que sean a la vez reflexivas, simétricas, antisimétricas y transitivas puede haber en un conjunto de n elementos. Demuestre que su conjetura es correcta.

6. Experimento de conteo a la Monte Carlo de relaciones de equivalencia: Escriba un programa que dado n, genere de manera aleatoria una relación que sea a la vez reflexiva y simétrica. Escriba un programa que dados n y k, realice k veces el experimento siguiente: Genera de manera aleatoria una relación que sea a la vez reflexiva y simétrica. Si ésta fuese también transitiva incrementa un contador. Luego de las k repeticiones, el programa ha de calcular la razón del contador entre k. ¿A cuáles valores, en función de n, esperaría usted que converjan esas razones, cuando k se incrementa arbitrariamente? Pruebe este programa para valores de n entre 20 y 100 y de k no menor que 10⁵.

7. Experimento de conteo a la Monte Carlo de relaciones de orden: Escriba un programa que dado n, genere de manera aleatoria una relación que sea a la vez reflexiva y antisimétrica. Escriba un programa que dados n y k, realice k veces el experimento siguiente: Genera de manera aleatoria una relación que sea a la vez reflexiva y antisimétrica. Si ésta fuese también transitiva incrementa un contador. Luego de las k repeticiones, el programa ha de calcular la razón del contador entre k. ¿A cuáles valores, en función de n, esperaría usted que converjan esas razones, cuando k se incrementa arbitrariamente? Pruebe este programa para valores de n entre 20 y 100 y de k no menor que 10⁵.

8. Escriba un programa que dado n, genere de manera aleatoria una relación de equivalencia en un conjunto A de n elementos. Para cada tal relación R, describa al cociente A/R y calcule el índice de R. Repita este experimento y grafique una tabla de frecuencias considerando los índices.

9. Escriba un programa que dado n, genere de manera aleatoria una relación de orden en un conjunto A de n elementos. Para cada tal relación R, dibuje a su gráfica dirigida G_(A,R): los nodos son los elementos de A y entre dos nodos x,y, $x\not=y$, habrá una arista de x a y si xRy y no hay un tercer elemento z tal que xRz y zRy.

10. Sea $\Sigma$ un alfabeto. Considere la relación de orden:

Prefijo:

Una palabra es menor que otra si es un prefijo de ella. $\forall \sigma_1, \sigma_2\in\Sigma^*$:

$$\sigma_1\leq_{\mbox{\scriptsize\it pre}} \sigma_2\ \Leftrightarrow\ \exists \tau\in\Sigma^*:\sigma_2=\sigma_1\tau.$$

Escriba programas para resolver cada uno de los problemas siguientes:

1.

Dadas dos palabras $\sigma_1,\sigma_2$ decida si acaso una es menor que la otra.

2.

Para un conjunto dado de palabras $S=\{\sigma_i\}_{1\leq i \leq m}$ calcule la matriz de orden $M=(m_{ij})_{i,j\leq n}$: $m_{ij}=1\Leftrightarrow \sigma_i\leq \sigma_j$. Una cadena es un subconjunto ordenado linealmente, es decir, cualesquiera dos elementos de ella se comparan entre sí. La cadena es maximal si no está contenida propiamente en ninguna otra. En este caso encuentre todas las cadenas maximales posibles.

11. Sea $\Sigma$ un alfabeto. Considere la relación de orden:

Monotonía:

Una palabra es menor que otra si todos sus símbolos aparecen, en el mismo orden, en ella. $\forall \sigma_1=s_{11}\cdots s_{1k_1}, \sigma_2=s_{21}\cdots s_{2k_2}\in\Sigma^*$:

$$\sigma_1\leq_{\mbox{\scriptsize\it mon}} \sigma_2\ \Leftright... ..._2]\mbox{\rm creciente },\forall j\leq k_1:s_{1j}=s_{2\phi(j)}.$$

Escriba programas para resolver cada uno de los problemas siguientes:

1.

Dadas dos palabras $\sigma_1,\sigma_2$ decida si acaso una es menor que la otra.

2.

Para un conjunto dado de palabras $S=\{\sigma_i\}_{1\leq i \leq m}$ calcule la matriz de orden $M=(m_{ij})_{i,j\leq n}$: $m_{ij}=1\Leftrightarrow \sigma_i\leq \sigma_j$. Encuentre todas las cadenas maximales posibles.

12. Sea $A=\{a_1,\ldots, a_n\}$ un conjunto de n elementos. Para cada operación binaria $\cdot:A\times A\to A$, consideremos su tabla de multiplicación $M=\left(m_{ij}\right)_{i,j\leq n}\in [\![1,n]\!]^{n\times n}$, tal que

$$\forall i,j\leq n:\ a_{m_{ij}}=a_i\cdot a_j$$

Escriba un programa que dados $n\in I\!\!N$ y una matriz $M\in [\![1,n]\!]^{n\times n}$ decida (de manera efectiva y eficiente) si la operación cuya tabla de multiplicación es M es:

1.

conmutativa,

2.

posee una unidad derecha,

3.

posee una unidad izquierda,

4.

asociativa,

5.

dado que existe una unidad, decidir si cada elemento posee un inverso,

6.

un monoide,

7.

un grupo.

13. Consideraremos conjuntos $A=\{a_1,\ldots, a_n\}$ de n elementos con una operación binaria $\cdot:A\times A\to A$, dada por su tabla de multiplicación $M=\left(m_{ij}\right)_{i,j\leq n}\in [\![1,n]\!]^{n\times n}$ en los que se define una relación de equivalencia mediante su matriz de adyacencia, $R\in \{0,1\}^{n\times n}$. Escriba un programa que dados $n\in I\!\!N$, una tabla de multiplicación $M\in [\![1,n]\!]^{n\times n}$ y una equivalencia $R\in \{0,1\}^{n\times n}$ decida (de manera efectiva y eficiente) si la equivalencia es congruente con la multiplicación. En tal caso, calcule la tabla de multiplicación del cociente A/R. Sugerencia: Ejemplifique considerando dos números primos p, q. Haga $n=p\cdot q$. Considere la operación $(i,j)\mapsto (i-1)(j-1)\mbox{\rm mod }n + 1$ y la relación $iRj\Leftrightarrow i\equiv j\mbox{\rm mod }p$. Ejemplifique también considerando la tabla de mutiplicación del grupo de permutaciones S_k, con k! elementos. Considere como relación $\phi R\psi$ si y sólo si la composición $\phi\circ \psi$ es una permutación par. (Revise un libro de Algebra Moderna, si fuera necesario, para aclarar la terminología que uso.)

14. Producto de monoides: Dados dos monoides $A_1=(A_1,\cdot_1,u_1)$ y $A_2=(A_2,\cdot_2,u_2)$ el monomio producto de ellos dos es $A_3=(A_3,\cdot_3,u_3)$, donde $A_3=A_1\times A_2$, la operación está definida ``componente-a-componente''

$$\cdot_3:\left((x_{11},x_{12})\; ,\;(x_{21},x_{22})\right) \ma... ...x_{22}) = \left(x_{11}\cdot_1 x_{21},x_{12}\cdot_2x_{22}\right)$$

y u₃=(u₁,u₂). Si n₁ es el número de elementos en A₁ y n₂ el de A₂ entonces su producto tendrá n₃=n₁n₂ elementos. Enumeremos a los elementos de A₃ como $\left(a_{k3}\right)_{k=1}^{n_3}$, donde $\forall i,j:\ a_{\phi(i,j)\;3}=(a_{i1},a_{j2})$, y $\phi:(i,j)\mapsto (i-1)n_2+j$. Escriba un programa que dados dos monoides A₁, A₂ con sendas tablas de multiplicación $M_1\in [\![1,n_1]\!]^{n_1\times n_1}$, $M_2\in [\![1,n_2]\!]^{n_2\times n_2}$, escriba la tabla de multiplicación del producto A₃, de acuerdo con la enumeración $\phi$.

15. Homomorfismo de monoides: Escriba un programa que dados dos monoides A₁, A₂ con sendas tablas de multiplicación $M_1\in [\![1,n_1]\!]^{n_1\times n_1}$, $M_2\in [\![1,n_2]\!]^{n_2\times n_2}$, decida si existe o no un homomorfismo $\phi:A_1\to A_2$. En caso de que exista, localice un homomorfismo, y de hecho a todos los posibles homomorfismos.

16. Sea Z_m el anillo de enteros módulo m. Sea $\mbox{\it Mat\/}_{n\times n}(Z_m)$ el conjunto de matrices $n\times n$ con entradas en Z_m. Con la multiplicación de matrices, $\mbox{\it Mat\/}_{n\times n}(Z_m)$ forma un monoide. Si $A,B\in\mbox{\it Mat\/}_{n\times n}(Z_m)$ son dos matrices, cualquier palabra $\sigma\in (A+B)^*$ determina una matriz en $\mbox{\it Mat\/}_{n\times n}(Z_m)$, a saber, la que se obtiene al interpretar la conjunción de dos símbolos como el producto de matrices. Introduzcamos la relación de equivalencia en (A+B)^* siguiente:

$$\sigma\equiv \tau\ \ \Leftrightarrow\ \ \sigma= \tau \mbox{\rm vistas como matrices en }\mbox{\it Mat\/}_{n\times n}(Z_m).$$

El cociente $(A+B)^*/\equiv$ resulta ser un submonoide de $\mbox{\it Mat\/}_{n\times n}(Z_m)$. Escriba un programa que dados m y n y dos matrices $A,B\in\mbox{\it Mat\/}_{n\times n}(Z_m)$ calcule a los elementos en $(A+B)^*/\equiv$ y a su tabla de multiplicación.

17. Dada una palabra $\sigma\in \Sigma$, un período es un prefijo $\tau$ de $\sigma$ tal que $\sigma$ es un prefijo de alguna potencia de $\tau$, es decir, $\sigma\leq_{\mbox{\scriptsize\it pre}}\tau^k$ para alguna k. Escriba un programa que dada una palabra $\sigma$ calcule todos sus períodos y escriba una lista de las longitudes de los períodos.

18. Una palabra $\sigma\in \Sigma$ se dice ser libre-de-cuadrados si no contiene ningún enfijo de la forma $\tau\tau$, con $\tau\not=\mbox{\it nil\/}$. Escriba un programa que dados n y m escriba una lista de todas las palabras de longitud a lo sumo n que están libres de cuadrados sobre el alfabeto de m símbolos $\{a,b,c,...,m\mbox{\rm -\'esima letra}\}$.

19. Sea A₁=(a+b) el alfabeto consistente de dos símbolos, y sea $A=A_1\cap A_1^2\cap A_1^3$ el lenguaje consistente de las 14 palabras de longitud a lo más 3 sobre A₁.

1.

Escriba un programa que dados n y un subconjunto no vacío $X\subset A$ enliste al conjunto X_n conformado por las palabras de longitud a lo más n formadas al concatenar partículas en X.

2.

Para cada n defina la relación de equivalencia: $X\equiv_n Y\Leftrightarrow X_n=Y_n$. Escriba un programa que dado n escriba la matriz de adyacencia de $\equiv_n$.

20. Dos palabras $\sigma, \tau$ se dicen conjugadas si existe una tercer palabra $\upsilon$ tal que $\sigma\upsilon=\upsilon\tau$. Esta relación es de equivalencia. Escriba un programa que dados m y n dé las clases de equivalencia de la relación de conjugación restringida a las palabras de longitud n sobre un alfabeto de m símbolos. Conjeture cuántas clases ha de haber, en términos de m y n.

21. Escriba un programa que dados m, y dos palabras $\sigma$ y $\tau$, sobre un alfabeto de m símbolos, donde $\sigma$ antecede a $\tau$ en el orden lexicográfico, calcule cuántas palabras están entre $\sigma$ y $\tau$ (contando a $\tau$ pero excluyendo a $\sigma$, según ese orden).

22. Derivación guiada en gramáticas formales: Escriba un programa que dada una gramática formal G=(V,T,P,s₀) le permita a un usuario derivar de manera interactiva palabras, seleccionando producciones a aplicarse en partículas de la palabra actual. En otras palabras, divida la pantalla en dos sectores, en cada uno de los cuales ha de poder hacerse ``scrolling''. En el primero se muestra las producciones enumeradas. En el segundo se deriva palabras. La palabra actual es la última línea de este segundo sector. El usuario ha de ``remarcar'' una partícula en la palabra actual, ha de indicar cuál producción quiere aplicar y el programa aplicará esa producción dejando el resultado como palabra actual.

23. Problema de la palabra en gramáticas libres de contexto: Escriba un programa que resuelva el Problema de la palabra en gramáticas libres de contexto, buscando derivaciones siniestras (``leftmost''). Para una gramática libre de contexto G=(V,T,P,s<sub>0</sub>) y una palabra dada $\sigma$ decida si acaso $\sigma\in L(G)$. Si $\sigma'=\tau A\tau_1$ es una palabra que posee un prefijo común con $\sigma$, $\tau$, consistente de símbolos terminales y A es un símbolo variable, entonces vea cuáles producciones con antecedente A tienen consecuentes que ``empaten'' con $\sigma$. Opte por las primeras. Proceda de esta forma hasta reconocer a $\sigma$. Si fallara entonces realice ``backtracking'' considerando otras producciones que empaten con $\sigma$.

24. Diseñe una gramática que genere al lenguaje

$$L_{\mbox{\scriptsize\it PotenciasDeDos}}=\{1^{2^n}\vert n\geq 0\}.$$

Escriba un programa que dado n muestre visualmente la manera en la que hay que aplicar las reglas para generar 1²ⁿ.

25. Diseñe una gramática que genere al lenguaje

$$L_{\mbox{\scriptsize\it Cuadrados}}=\{1^{n^2}\vert n\geq 2\}.$$

Escriba un programa que dado n muestre visualmente la manera en la que hay que aplicar las reglas para generar 1ⁿ². Sugerencia: Observe que para todo $n\geq 0:\ (n+1)^2=n^2 + 2n + 1$.

26. Diseñe una gramática que genere al lenguaje

$$L_{ijij}=\{a^ib^ja^ib^j\vert i,j\geq 1\}.$$

Escriba un programa que dados i,j muestre visualmente la manera en la que hay que aplicar las reglas para generar aⁱb^jaⁱb^j.

27. Considere a la gramática con producciones

$$S\rightarrow DAI\vert a\ \ ;\ \ D\rightarrow S\vert d\ \ ;\ \ A\rightarrow S\vert a\ \ ;\ \ I\rightarrow S\vert i$$

Escriba un programa que dado $n\geq 0$ genere una palabra terminal de longitud 2n+1. Escriba un programa que dado $n\geq 0$ cuente el número total de derivaciones posibles para arribar a una palabra de longitud 2n+1.

28. Cuenta de palabras en gramáticas libres de contexto: Escriba un programa que para una gramática libre de contexto G=(V,T,P,s₀) y para un número n cuente cuántas palabras de longitud n se derivan en G.
Siguiente: Autómatas finitos y expresiones Un nivel arriba: Gramáticas formales Anterior: Ejercicios