Esta página ofrece ejercicios corregidos sobre el teoría del lenguaje, más precisamente en autómatas alimentados por batería.

Ejercicio 1

los 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 → aS | aSb | ε

Ejercicio 2

Qué idioma es generado por la siguiente gramática:

S → aSa | aBa

B → bB | B

dar elautó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:

ejercicios corregidos sobre la teoría de los lenguajes pushdown autómatas

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.

ejercicios corregidos sobre la teoría de los lenguajes pushdown autómatas

Derivación de la palabra ab:

ejercicios corregidos sobre la teoría de los lenguajes pushdown autómatas

Derivación de la palabra abb:

ejercicios corregidos sobre la teoría de los lenguajes pushdown autómatas

Derivación exitosa de las palabras aaaa y baab:

ejercicios corregidos sobre la teoría de los lenguajes pushdown autómatas

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.

ejercicios corregidos sobre la teoría de los lenguajes pushdown autómatas

Con lambda la letra vacía.

Ejercicio 5

Sea el alfabeto A = {a, b} y el idioma 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.

ejercicios corregidos sobre la teoría de los lenguajes pushdown autómatas

Z es el símbolo que se coloca en la pila en la inicialización (símbolo del final de la pila).

Ejercicio 6

Escribe una gramática algebraica que pueda escribir cualquier expresión regular con el alfabeto {0,1}. Para información, la gramática algebraica contiene el alfabeto {0,1,(,), ∪,*, ∅, ε }. Prueba en 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:

ejercicios corregidos sobre la teoría de los lenguajes pushdown autómatas

Lo que da el siguiente árbol de derivación:

ejercicios corregidos sobre la teoría de los lenguajes pushdown autómatas

Compartir, repartir
es_ESES