
Conceptos básicos
Def. Un símbolo es cualquier carácter imprimible.
Def. Una cadena es una secuencia finita de símbolos.
Def. La longitud de una cadena w, se denota |w| y su valor es igual al
número de símbolos contenidos en dicha cadena.
Def. La cadena vacía , es la cadena consistente de cero símbolos
(|| =0).
Def. Un prefijo de una cadena es cualquier número de símbolos al inicio
de la misma.
Def. Un sufijo de una cadena es cualquier número de símbolos al final
de la misma.
Conceptos Básicos
Def. La concatenación de dos cadenas es la cadena
formada al escribir la primera cadena seguida de la
segunda.
Ej. Si u y v son dos cadenas tales que u = abab y
v = cdcd entonces:
uv = ababcdcd
vu = cdcdabab
Conceptos Básicos
Propiedades de la concatenación
Sean u, v y w tres cadenas cualquiera, entonces tenemos:
1.
2.
Cerradura. Si u y v son cadenas, uv también lo es.
Conmutatividad. La concatenación no es conmutativa:
uv  vu
3.
Asociatividad. La concatenación es asociativa:
(uv)w = u(vw)
4.
La cadena vacía es la identidad con respecto a la operación de
concatenación:
u =  u = u
Conceptos Básicos
Def. Un alfabeto es un conjunto finito, no vacío, de símbolos.
Def. Un lenguaje (formal) es un conjunto de cadenas finitas de símbolos
tomadas a partir de un cierto alfabeto.
Def. El conjunto vacío , y el conjunto {} son lenguajes. (note que son
distintos conjuntos; el segundo tiene un elemento, mientras que el
primero ninguno, || = 0 y |{}| = 1).
Def. Un palíndrome, sobre un alfabeto, es una cadena que se lee igual en
una dirección que en otra.
Ej.
 = { 0, 1}
palíndromes sobre  = {, 0, 1, 00, 11, 000, 111, 010, 101, 01110, …}
Nota: El conjunto de palíndromes no forma un lenguaje.
Conceptos Básicos
Si generalizamos la operación de concatenación sobre un
conjunto A={a} tenemos:
A0 = 
A1 = {a}
AA = A2 = {aa}
A2 A = A3 = {aaa}
…
A* = A0 A1  A2  … = { , a, aa, aaa, aaaa, …}
Conceptos Básicos
Def. Dado un alfabeto  cualquiera, es posible crear el
lenguaje de todas las cadenas que se pueden generar a
partir del mismo utilizando concatenación. A este
lenguaje se le denomina Cerradura de Kleene sobre  ,
denotado *.
ej.  = {a, b}
* = { , a, b, aa, ab, ba, bb, aaa, aab, …}
Expresiones Regulares
Def. Sea L un conjunto de cadenas formadas con elementos del alfabeto . Se
denomina a L un conjunto regular si puede ser generado a partir ,
utilizando tan solo las operaciones de unión, concatenación y cerradura
de Kleene.
Def. Sea  un alfabeto cualquiera. Las expresiones regulares sobre  se definen
de la siguiente manera:
i)
Ø (conjunto vacío) es una expresión regular.
ii)
 (la palabra vacía) es una expresión regular.
iii)
Si a  , entonces a es una expresión regular.
iv)
Sean u y  expresiones regulares sobre , entonces:
u +  , u y u* son expresiones regulares sobre .
iii)
Ninguna expresión que no este definida en i y iv es expresión regular
sobre .
Expresiones Regulares
La notación
u+= uu* ,
u2 = uu, u3= uu2, un = u un-1
Ejemplos de expresiones regulares:
(a) 00
(b) (0 + 1)*
(c) (0 + 1)*00(0 + 1)*
(d) (1 + 10)*
Indique que lenguaje define cada una de las expresiones
mostradas.
Descargar

Cb00003 Teoria de Lenguajes