Scribd
Cargar
162 vistas3 páginas

Gramáticas Regulares y Autómatas

Este documento presenta varios ejercicios sobre gramáticas formales, incluyendo gramáticas regulares, libres de contexto y sus formas normales. Los ejercicios piden construir gramáticas para describir lenguajes formales, convertir autómatas a gramáticas y viceversa, y transformar gramáticas a sus diferentes formas normales.

Cargado por

Brian Chura Siñani
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd
162 vistas3 páginas

Gramáticas Regulares y Autómatas

Este documento presenta varios ejercicios sobre gramáticas formales, incluyendo gramáticas regulares, libres de contexto y sus formas normales. Los ejercicios piden construir gramáticas para describir lenguajes formales, convertir autómatas a gramáticas y viceversa, y transformar gramáticas a sus diferentes formas normales.

Cargado por

Brian Chura Siñani
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd

PRÁCTICA GRAMÁTICAS

Gramáticas Regulares
1. Encuentre la gramática regular izquierda o derecha que genera los siguientes
lenguajes:
a. L = {w ε {a, b, c} * / w termina aabc}
b. L = {w ε{a, b} * / w no termina en ab}
c. L = {w ε{a, b, c} * / bac es subcadena de w}.
2. Convertir a autómatas los lenguajes generados por las siguientes gramáticas:
a. S → aS
S → aA
A → cS

b. S → bA
A → aA
B → Abc
A →a
3. Para los siguientes lenguajes construya una gramática regular derecha que
los genere:
a. L = {w ε{a, b}* / w contiene b y no contiene la subcadena aa}.
b. L = {w ε{0, 1}* / son enteros binarios divisibles entre 3}.
c. L = {w ε/ termina en b y toda c va seguida por una a}.
4. Encuentre una gramática regular que genere el mismo lenguaje que:
aa* (ab + a)* .
5. Construir gramáticas lineales derecha e izquierda para el lenguaje.
m
L = {an b : n ≥ 2, m ≥ 3}
6. Encuentre una gramática regular que genere el lenguaje.
L = {w ε{a, b}* / na (w) + 3 × nb (w) es par}
7. Dadas las siguientes gramáticas regulares derechas encontrar el lenguaje
que generan:
a. S → bS | aA
A → bA | aB | a
B → bB | aA | b

b. S → aA | bB
A → aS | bC | a
B → aC | bD
C → aB | bE
D → aE | bS | b
E → aD | bA
Gramáticas libres de contexto
1. Construir la gramática equivalente a los siguientes autómatas:
a.

b.

c.

2. Encuentre una gramática libre de contexto que genere el lenguaje:


a. L = {an bm : n ≤ m + 3}
b. L = {an bm : n =/ m − 1}
c. L = {an bn ck : k ≥ 3, n >= 0}
3. ​Convertir las siguientes gramáticas a su Forma Normal de Chomsky:
a. S → aX | Y b
X →S|λ
Y → bY | b

b. S → AA
X → B | BB
Y → abB | b | bb

c. S → X AX | AX | XA | BX | AB | a | b
X → X AX | AX | XA | XBX | BX | XB | a | b
A→a
B→b

d. S → X aX | bX | Y
X → X aX | XbX | λ
Y → ab

e. S → aX | Y | bab
X → λ|Y
Y → bb | bXb
S
4. ​Convertir las siguientes gramáticas a su Forma Normal de Greibach:
a. S → X A | BB
B → b | SB
X→ b
A→a

b. S → A
A → aBa | a
B → bAb | b

c. S → X bY | Y | bab
X → aX | a
Y → bY | a

d. S → aSb | bSa | A | B
A → Aa | b
B → Bb | b

e. S → aSc | T
T → bT c | λ
5.​ ​Seleccione tres incisos del ejercicio 3 y conviértelos a la 3FN.
6.​ ​Seleccione tres incisos del ejercicio 4 y conviértelos a la 3FN.

También podría gustarte