1.3 Lenguajes

1.3 Lenguajes
Un lenguaje sobre el alfabeto A es un subconjunto del conjunto de las cadenas sobre A: L ⊆ A ∗ . Los lenguajes los notaremos con las letras intermedias del alfabeto latino en mayúsculas.

Ejemplo:  Los siguientes son lenguajes sobre un alfabeto A, cuyo contenido asumimos conocer claramente: L1 = {a,b, ε}, símbolos a, b y la cadena vacía L2 = {a ib i | i = 0,1,2,...}, palabras formadas de una sucesión de símbolos a, seguida de la misma cantidad de símbolos b.
L3 = {uu−1 | u ∈ A ∗}, palabras formadas con símbolos del alfabeto A y que consisten de una palabra, seguida de la misma palabra escrita en orden inverso.

L4 = {a n 2 | n = 1,2,3,...}, palabras que tienen un número de símbolos a que sea cuadrado perfecto, pero nunca nulo. Aparte de las operaciones de unión e intersección de lenguajes, dada su condición de conjuntos existe la operación de concatenación.

If L1,L2 son dos lenguajes sobre el alfabeto A, la concatenación de estos dos lenguajes es el que se obtiene de acuerdo con la siguiente expresión, L1L2 = {u1u2 | u1 ∈ L1,u2 ∈ L2}

Propiedades: L0/ = 0/L = 0/ (0/ es el Lenguaje que contiene 0 palabras) Elemento Neutro.- {ε}L = L{ε} = L Asociativa.- L1(L2L3) = (L1L2)L3 La iteración de lenguajes se define como en las palabras, de forma recursiva: Definición 10 Si L es un lenguaje sobre el alfabeto A, entonces la iteración de este lenguaje se define de acuerdo con las siguientes expresiones recursivas, L 0 = {ε} L i+1 = L iL Definición 11 Si L es un lenguaje sobre el alfabeto A, la clausura de Kleene de L es el lenguaje obtenido de acuerdo con la siguiente expresión: L ∗ = [ i≥0 L i Definición 12 Si L es un lenguaje sobre el alfabeto A, entoces L + es el lenguaje dado por: L + = [ i≥1 L i Propiedades: L + = L ∗ si ε ∈ L.
_________________________________________________________________________________
Equipo: Anahi Jaramillo Hernandez, Erick Rios Garcia. Luis Antonio Martinez Sanchez.Alejandro Gomez Perez.