Lenguajes Y Gramaticas

CAPITULO 1. LENGUAJES Y GRAMATICAS 2
1.1 Introducción. 3
1.2 Lenguajes Formales. 3
1.3 Alfabeto, Palabras. Operaciones con palabras. Lenguajes formales. 3
1.4 Operaciones con lenguajes 3
1.5 Unión. Concatenación. Potencia. Clausura. 3
1.6 Gramáticas Formales 3
1.7 Concepto de Gramática Formal 3
1.8 Producciones. Gramática Formal. Lenguaje asociado a una gramática. 3
1.9Tipos de gramáticas. 3
1.10 Jerarquía de Chomsky. Gramáticas de tipo 0, 1, 2 y 3. 3
1.11 Arboles de derivación. 3
1.12 Actividades y ejercicios. 3
1.13 Tarea 1. 3
1.14 Tarea 2. 3
1.15 Tarea 3. 3
1.16 Examen I 3

CAPITULO 1. LENGUAJES Y GRAMATICAS

1.1 Introducción.

1.2 Símbolos y Alfabetos

Un símbolo es un signo, digito, letra o incluso un grupo deletras que se utiliza en algún lenguaje y que tiene algún significado por sí mismo.

EJEMPLOS DE SIMBOLOS: 0, 1, W, Ok, b, Ω, ∑, etc.

Un alfabeto es un conjunto finito no vacio de símbolos y se denota por ∑.

EJEMPLO 1
∑= {0,1} es un alfabeto

EJEMPLO 2
El alfabeto griego es ∑= {ε, θ, λ,….., μ, β, δ, ε, ω}

EJEMPLO 3
Otro alfabeto puede ser: ∑= {READ, INPUT, GET, FOR, ….IF}Propiedades de los alfabetos

Los alfabetos comparten las propiedades que son comunes a cualquier otra clase de conjuntos, es decir, sean ∑1 y∑2 son dos alfabetos, entonces si el resultado de las siguientes operaciones:
Σ1 ⋃ Σ2, Σ1 ∩ Σ2, Σ1- Σ2, Σ2- Σ1, Σ1 ⨁ Σ2 son conjuntos no vacios, son alfabetos.

EJEMPLO 1
Sean los alfabetos Σ1={0,1,2,3,4} y Σ2={0,2,a,b}, entonces tenemos que también sonalfabetos los siguientes:

Σ1 ⋃ Σ2={0,1,2,3,4,a,b}
Σ1 ∩ Σ2={0,2}
Σ1- Σ2={1,3,4}
Σ2- Σ1={a,b}
Σ1 ⨁ Σ2=1,3,4,a,b

1.3 Palabras o Cadenas
Una cadena o palabra es una secuencia finita de simbolos yuxtapuestos de un alfabeto dado.

EJEMPLO 1
Sea Σ1={0,1}, entonces w1=10, w2=10011 y w3=100100101 son cadenas o palabras formadas apartir del alfabeto.

EJEMPLO 2
Sea Σ1={a,b,c,d,e}, x1=adce,x2=aaaaa, x3=cabe, x4=decada y x5=c son cadenas o palabras formadas a partir de ese alfabeto.
Cadena Vacía
La cadena vacía se denota por ε y es la cadena que está formada por una secuencia vacía de simbolos bajo cualquier alfabeto.

1.4 Operaciones con cadenas o palabras

Longitud de una cadena
Si w es una cadena, decimos que la longitud de la misma es el numero de simbolos que laforman y se denota por |w|.

EJEMPLO 1

Sea w1=101011, entonces |w1|=6 y sea w2=10110100101, entonces |w2|=11.
La longitud de la cadena vacía es cero: | ε |=0

Concatenación
Concatenación es yuxtaposición de dos cadenas, una a continuación de la otra, de tal forma que si w y x son dos cadenas, la concatenación de w con x es la cadena que se obtiene de añadir x a la cadena w. La concatenaciónse denota con el operador de yuxtaposición: w∙x, pero usualmente se omite el punto, quedando wx.

EJEMPLO 1
Sea w= sofá y x=cama entonces w∙x=sofacama, mientras que x∙w =camasofa.

La longitud de la concatenación es igual a la suma de las longitudes de las cadenas individuales: |wx|=|w|+|x|.

En el ejemplo anterior w y x son dos cadenas de longitud 4 y w∙x es de longitud 8.

EJEMPLO 2:Sean w=so y x=pa, entonces xw=paso y wx=sopa.

La concatenación de ε con cualquier cadena w no modifica a w. Es decir, la cadena vacia es el idéntico respecto a la concatenación, ya que: εw=wε=w.

Potencia de cadenas
Sea w una cadena, entonces para cualquier n∈N se tiene que la enésima potencia de w se define como:

wn=ε para n=0w wn-1 para n>0

EJEMPLO 1
Sea w=abcentonces w0=ε, w1=ww0=abcε=abc, w2=ww1=abcabc y
w3=ww2=abcabcabc.

EJEMPLO 2
Sea w=0 entonces w0= ε, w1=0, w2=00, w3=000, w4=0000, etc.

EJEMPLO 3
Sea w=ε, entonces w0=w1=w2=w3=….=ε.

En general se cumple que (wx)n≠wnxn, como se puede verificar en el siguiente ejemplo:

EJEMPLO 4

Sea w=01 y x=10, entonces (wx)2=(0110)2=01100110, mientras que
w2x2=(01)2(10)2=01011010.

Prefijo
Se...