CADENAS DE LENGUAJE
Esta consiste en una secuencia de símbolos yuxtapuestos (se coloca uno seguido del otro).
Sean:
? = {0,1,2}
W = 0 x = 02 y = 011 z = 12012
En este caso w, x, y, z soncadenas formadas con símbolos del alfabeto
* CADENA VACIA
Es aquella cadena que no tiene símbolos. Aquí se tiene que £w = w£ y ££ = £.
Si w = pera, entonces
£w = pera = w£
* INVERSA DEUNA CADENA.
Es la cadena que se obtiene al escribir los caracteres en forma invertida.
Sea w = Hola, entonces
W1 = (Hola)1 = (ola)1H = (la)1Oh = (a)1 loH = (?)1aloH = aloH
* CADENA ELEVADA A UNAPOTENCIA
Si n es un elemento del conjunto de números naturales (n ? N ) y w es una cadena, entonces:
W0 = £ (cadena vacia)
W1 = WW0
W2 = WW1 = WWW0
W3 = WW2 = WWW1 = WWWW0
Wn =WWn-1
SeaW=Hola, entonces
W4 = WW3 = WWW2 = WWWW1 = WWWWW0 = HolaHolaHolaHola? = HolaHolaHolaHola
OPERACIONES DE CADENAS Y LENGUAJES
Considerado que un lenguaje es un conjunto de símbolos o palabras sobre unalfabeto, se puede llevar acabo algunas operaciones de conjuntos como la unión, intersección, diferencia y complementación.
Sean L y M lenguajes, entonces
LENGUAJES REGULARES
Con el alfabeto ? esposible formar una gran cantidad de lenguajes, pero no existe un método efectivo para saber cuantos de ellos son regulares. Todos los lenguajes sobre ? son sublenguas de lenguaje universo ?*, enlugar de ello se utilizaran algunas propiedades de los lenguajes para determinar cuales de ellos son regulares. El conjunto de lenguajes regulares sobre ? son:
* El lenguaje vacio
* El lenguajeque contiene la cadena vacia como único elemento { ? }
* El lenguaje unitario { a } es regular V a ? ?.
* Si L Y M son lenguajes, entonces también lo son el lenguaje que resulta de la unión (L?M ), la concatenación (L M ), la potenciación (Ln o Mn) y la cerradura de Kleene (L*).
* Ningún otro lenguaje sobre ? es regular.
Se puede concluir que apartir del alfabeto ? los lenguajes…
