Esta página ofrece ejercicios corregidos sobre: autómata a pilas.
Ejercicio 1
La gramática (lineal) S → aSb | ε produce el lenguaje {anoBno : n ≥ 0}. Según este ejemplo, sugiera gramáticas para cada uno de los siguientes idiomas: {a2n(antes de Cristo)3n : n ≥ 0}, {a2nB3vs20n : n ≥ 0}, {a2nB3nvs20 : n ≥ 0}, {ametroBno : m ≥ n ≥ 0}
1 – S → aaSbcbcbc | ε
2 – S → aaSc20 | bbb
3 – S → Xc20; X → aaXbbb | ε
4 – S → unS | aSb | ε
Ejercicio 2
Qué idioma es generado por la siguiente gramática:
S → aSa | aBa
B → bB | B
Dar el autómata a batería generado por el siguiente lenguaje: L (G) = {anoBmetrovsmetroD2n | n≥0, m> 0}.
En gramática, la primera regla genera de forma recursiva tantos a en cada extremo de la palabra. La segunda regla genera al menos una b dentro de la palabra. Por tanto, el lenguaje generado es L (G) = {anoBmetroParano | n> 0, m> 0}.
Antes de construir el autómata, primero debe comprender las reglas gramaticales. Notamos que las extremidades están en el poder n mientras que el centro en el poder m. Por tanto, el lenguaje se puede generar mediante reglas del tipo A → aAa | B. De aquí deducimos las dos reglas que generan el lenguaje S → aSdd | PARA ; A → bAc | antes de Cristo
Ejercicio 3
Tomamos un autómata que produce en palíndromo, es decir, palabras que se pueden leer de la misma manera, ya sea en lectura izquierda o derecha. El autómata es entonces:
Da la tabla de transición y todas las derivaciones de las palabras ab y abb. Luego demuestre mediante una derivación exitosa que las palabras aaaa y baab son palíndromos.
Derivación de la palabra ab:
Derivación de la palabra abb:
Derivación exitosa de las palabras aaaa y baab:
Ejercicio 4
Sea el alfabeto A = {a, b} y el idioma L = {a * b}. Escribe la gramática de este idioma. Encuentre un autómata a batería que pueda leer este idioma.
G = {T = {a, b}, N = {S}, S = {S}, P = {S -> b, S -> aS}}
Aquí notamos que la pila no es útil, el uso nulo de una pila equivale a usar una letra vacía.
Con lambda la letra vacía.
Ejercicio 5
Sea el alfabeto A = {a, b} y la lengua L = {ano Bpag / n> = 0 y n <= p <= 2n}. Escribe la gramática de este idioma y demuestra que es un idioma algebraico. Encuentre un autómata a batería que pueda leer este idioma.
G = {T = {a, b}, N = {S}, S = S, P = {S -> ε | aSb | aSbb}}
También podemos escribir la gramática de la siguiente manera
Tenga en cuenta que las reglas respetan el formato de las gramáticas de tipo 2. Sin embargo, esta gramática no respeta el formato de tipo 3.
Z es el símbolo que se coloca en la pila en la inicialización (símbolo de fin de pila).
Ejercicio 6
Escribe una gramática algebraica que pueda escribir cualquier expresión regular con el alfabeto {0,1}. Para obtener información, la gramática algebraica contiene el alfabeto {0,1, (,), ∪, *, ∅, ε}. Prueba en la expresión regular (0 ∪ (10) * 1) *
Tomemos las reglas para formar una expresión regular:
0 o 1 solamente: S → 0 | 1
Palabra vacía o épsilon: S → ∅ | ε
Unión de dos subpalabras: S → S ∪ S
Concatenación de dos subpalabras: S → SS
Estrella de una subpalabra: S → S *
Paréntesis de prioridad: S → (S)
Al tomar la palabra obtenemos las siguientes derivaciones:
Lo que da el siguiente árbol de derivación:
