Siguiente: Programas Un nivel arriba: Gramáticas formales Anterior: Tipos de gramáticas

Ejercicios

1. Para la gramática G cuyas producciones son

$$S\rightarrow SS\vert aSb\vert bSa\vert ab\vert ba$$

describa al lenguaje generado por G.

2. Considere las gramáticas G₁,G₂ cuyas producciones son

$$\begin{eqnarray*}G_1 &:& \begin{array}[t]{rcl} S &\rightarrow& \mbox{\it nil\/}... ...it nil\/}\vert A \\ A &\rightarrow& cAd\vert cd \end{array} \end{eqnarray*}$$

a. Derive, en cada una de las gramáticas, dos palabras de longitud 4. b. Calcule L(G₁) y L(G₂)

3. Considere la gramática G cuyas producciones son

$$\begin{eqnarray*}S &\rightarrow& aB\vert ba \\ A &\rightarrow& a\vert aS\vert bAA \\ B &\rightarrow& b\vert bS\vert aBB \end{eqnarray*}$$

y la palabra $\sigma=a^3b^2ab^3a$. a. Encuentre una derivación diestra de $\sigma$. b. Encuentre una derivación siniestra de $\sigma$. c. Bosqueje un procedimiento tal que dada una palabra decida si acaso está generada en la gramática y, en tal caso, encuentre una derivación diestra.

4. Construya una gramática que genere al lenguaje

$$L=\{a^ib^jc^k\vert(i\not=j)\lor(j\not=k)\}.$$

Explique su estrategia.

5. Construya una gramática que genere al lenguaje

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

Explique su estrategia.

6. Construya una gramática que genere al lenguaje

$$L=\{\sigma\in(0+1)^*\vert\sigma \mbox{\rm posee el mismo n\'umero de 0's y 1's}\}.$$

Explique su estrategia.

7. Construya una gramática que genere al lenguaje

$$L=\{0^m1^n\vert m>n\geq 0\}.$$

Explique su estrategia.

8. Construya una gramática que genere al lenguaje

$$L=\{0^n1^k\vert 1\leq n\leq 2^k\}.$$

Explique su estrategia.

9. Construya una gramática que genere al lenguaje

$$L=\{0^n1^m0^k\vert k=n+m\}.$$

Explique su estrategia.

10. Construya una gramática que genere al lenguaje

$$L=\{1^x01^y01^z\vert z=xy, \;x,y\geq 0\}.$$

Explique su estrategia.

11. Construya una gramática libre de contexto que genere a las expresiones aritméticas de C, considerando las prioridades usuales.

12. Construya una gramática lineal izquierda que genere al lenguaje 10^*.

13. Construya una gramática lineal derecha que genere al lenguaje ab^*+c^*.

14. Dadas dos gramáticas G₁,G₂ construya una gramática para generar cada uno de los siguientes lenguajes: $L(G_1)\cup L(G_2), L(G_1) L(G_2),L(G_1)^*$. Muestre que si ambas gramáticas son libres de contexto entonces también pueden serlo las gramáticas de los anteriores lenguajes.

15. Sea G la gramática con producciones

$$\begin{eqnarray*}\left.\begin{array}{rcl} S &\rightarrow& YXY \end{array}\ri... ...x{\it nil\/} \end{array}\right\} &:& \mbox{\rm terminaci\'on} \end{eqnarray*}$$

y símbolo inicial S. a) Derive a las palabras 1⁴,1⁸,1¹⁶. b) Demuestre que el lenguaje de la gramática es $\{1^{2^n}\vert n\geq 1\}$.

16. Sea G la gramática con producciones

$$\begin{eqnarray*}\left.\begin{array}{rcl} S &\rightarrow& 1 \\ S &\rightarr... ...rrow& 1VVCU \end{array}\right\} &:& \mbox{\rm reiteraci\'on} \end{eqnarray*}$$

y símbolo inicial S. a) Derive a las palabras 1²,1⁴,1⁹,1¹⁶. b) Demuestre que el lenguaje de la gramática es $\{1^{n^2}\vert n\geq 1\}$. Sugerencia: Recuerde que para todo $n\geq 1$, $\sum_{i=1}^n (2i-1)=n^2$.

17. Sea G la gramática con producciones

$$\begin{array}{rrcll} 1. & S &\rightarrow& IMaD &\mbox{\it\be... ...nipage}[t]{20em} term\'\i nese. \end{minipage}\/} \end{array}$$

y símbolo inicial S. a. Genere al menos tres palabras en esa gramática. b) Conjeture cuál conjunto es L(G) y demuestre su conjetura.

18. Para cada $m\geq 0$ calcule el número de cadenas equilibradas de de paréntesis de longitud 4n=2m.

19. Construya todos los árboles de derivación de la palabra abababa en la gramática $S\rightarrow SbS\vert a$.

20. Dado un triángulo (no-degenerado) su centro es el punto donde se cruzan las bisectrices de cada uno de los ángulos del triángulo. Sea $\Phi$ el procedimiento que dado un triángulo, une su centro con cada uno de sus vértices de manera que el triángulo queda dividido en tres ``subtriángulos''. Las triangulaciones de un triángulo inicial se definen como sigue:

• El triangulo inicial es en sí una triangulación.
• Si ${\cal T}$ es una triangulación, al elegir un subtriángulo cualquiera de ella y aplicarle el procedimiento $\Phi$ se obtiene una nueva triangulación.

a. Muestre que un número n es impar si y sólo existe una triangulación de n subtriángulos a partir de cualquier triángulo inicial. b. Describa una gramática formal que genere al conjunto de triangulaciones. c. Cuente el número de triangulaciones. d. Diremos que dos triangulaciones, de un triángulo equilátero, son equivalentes si una se obtiene de la otra mediante una isometría del triángulo Para una triangulación dada, calcule el número de triangulaciones que le son equivalentes.
Siguiente: Programas Un nivel arriba: Gramáticas formales Anterior: Tipos de gramáticas