Tareas

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...