LOSQUIMICOS_OORM_ACT 5

Ramos Mora Jorge Eduardo Teoría de la Computación

ACTIVIDAD IV: LENGUAJES REGULARES, EXPRESIONES REGULARES, Y

GRAMÁTICAS REGULARES

1.- Generar la gramática regular que considere cadenas de longitud 3 sobre el alfabeto de terminales ΣT= {a, b}.

P={S::=aA|bA

A::=aB|bB

B::=a|b}

2.- Elabore una lista con todas las frases generadas por la gramática del cuadro 1 y cree el árbol de derivación correspondiente.

⟨frase⟩ ⟨sujeto⟩ ⟨predicado⟩ ⟨punto⟩

⟨sujeto⟩ ⟨sustantivo⟩⟨predicado⟩ ⟨punto⟩

⟨sustantivo⟩ Juan

⟨sustantivo⟩ ⟨sustantivo⟩

⟨predicado⟩ ⟨verbo intransitivo⟩

⟨predicado⟩ ⟨verbo transitivo⟩ ⟨objeto⟩

⟨verbo intransitivo⟩ patinar

⟨verbo transitivo⟩ golpear

⟨verbo transitivo⟩ golpear

⟨objetivo⟩ a ⟨sustantivo⟩

⟨punto⟩ 

⟨frase⟩ Juan ⟨predicado⟩ ⟨punto⟩ ⟨frase⟩

⟨frase⟩ Juan patinar ⟨punto⟩

⟨frase⟩ Juan patinar. ⟨sujeto⟩ ⟨predicado⟩ ⟨punto⟩

Juan patinar .

⟨frase⟩ Juan ⟨predicado⟩ ⟨punto⟩ ⟨frase⟩

⟨frase⟩ Juan golpear ⟨objeto⟩⟨punto⟩

⟨frase⟩ Juan golpear a ⟨sustantivo⟩⟨punto⟩ ⟨sujeto⟩ ⟨predicado⟩ ⟨punto⟩

⟨frase⟩ Juan golpear a Juan⟨ punto⟩

⟨frase⟩ Juan golpear a Juan . Juan ⟨verbo transitivo⟩ ⟨objeto⟩ .

Golpear a ⟨sustantivo⟩

Juan

3.- Demuestre que si los siguientes lenguajes L1 y L2 son regulares, entonces los siguientes lenguajes también lo son. Puede usar cualquier técnica de demostración que desee.

a)L1 •L2 si lo son ya que representa la concatenación

Si y son e. r. entonces αβtambién lo es y representa al lenguaje Lαβ=Lα.Lβ

b) L 1 si, porque es la cerradura de kleene y obtendría todas las palabras al infinito con el numero 1

c)L1L2 si lo es,representa la unión de todas las cadenas entre dichos lenguajes

Si y son e. r. entonces α+βtambién lo es y representa al lenguaje Lα+β=Lα∪Lβ

9.- Describir los lenguajes representados por las siguientes expresiones regulares definidas sobre el

alfabeto Σ = {a, b, c}

1. (a+b)c se toman las palabras a o b concatenado con c,las veces que sean

2. (aa+)(bb) se pueden tomar todas las a, y además se puede generar el vacio con

...