automaras

Trabajo VII

Semestre A2005

Teoría

Lenguajes y Autómatas finitos

1.

Lenguajes. Conceptos fundamentales

Sea Σ una colección finita de símbolos. Este conjunto de símbolos se denomina alfabeto y los elementos letras. Una palabra sobre Σ es una cadena de
longitud finita de elementos de Σ. La cadena vacía o cadena nula, denotada por
ε, es una cadena que no contiene símbolos. Elconjunto de todas las palabras
sobre Σ se denota Σ∗ . ε es una palabra en cualquier alfabeto Σ. Un lenguaje
sobre Σ es un subconjunto de Σ∗ . Si L denota el conjunto de los lenguajes sobre
Σ se tiene que L = {L : L ⊂ Σ∗ }
Note que ε, la cadena vacía, es la cadena que no contiene símbolos. Es diferente de ∅ el conjunto vacío (lenguaje vacío). Se sigue que {ε} es el conjunto
que contiene exactamenteuna cadena, de hecho, la cadena vacía.
La longitud de una palabra u ∈ Σ∗ , denotada por |u|, es el número de
posiciones que tiene la palabra. Se puede definir recursivamente de esta manera:
|ε| = 0
|ua| = |u| + 1
donde u ∈ Σ∗ y a ∈ Σ.
De este modo una palabra u ∈ Σ∗ se puede definir por una función u :
{1, 2, . . . , |u|} → Σ donde u(i) es la letra que se encuentra en la posición i en lapalabra u.
Dos palabras u, v ∈ Σ∗ son iguales si |u| = |v| y u(i) = v(i) para 1 ≤ i ≤ |u|.
Definimos una operación sobre Σ∗ denominada concatenación. Para u, v ∈
Σ∗ la concatenación de u y v se denota uv y se define a través de la función
uv : {1, 2, . . . , |u| + |v|} → Σ
uv(i) =

u(i),
v(i − |u|),

si 1 ≤ i ≤ |u|
si |u| + 1 ≤ i ≤ |u| + |v|

Así la palabra uv es la palabra que seobtiene escribiendo las letras de u y
luego las letras de v. Si u = u1 u2 · · · uk y v = v1 v2 · · · vs entonces uv =
u1 u2 · · · uk v1 v2 · · · vs donde ui , vj ∈ Σ. Se deja al lector verificar que esta operación es asociativa.
Ejercicio 1 Pruebe que |uv| = |u| + |v|
Definición 1 Dados dos lenguajes L, M ∈ L, la concatenación de los lenguajes
L y M se denota por LM y se define
LM = {vw : v ∈ L, w∈ M }
Matemáticas Discreta

Prof. José Luis Chacón

Pensar y actuar

Trabajo VII

Semestre A2005

Teoría

Es fácil ver que la concatenación de lenguajes es asociativa.
Ejemplo 1 Sean Σ = {0, 1} y L, M dos lenguajes sobre Σ dados por L =
{1, 10} y M = {1, 01} entonces LM = {11, 101, 1001}. Mientras que M L =
{11, 110, 001, 0110}.
Definición 2 Si Σ es un alfabeto y n ∈ N se define laspotencias de Σ recursivamente de la siguiente manera:
1)

Σ1 = Σ

2)

Σn+1 = ΣΣn

Por convención se tiene que Σ0 = {ε}.
Ejemplo 2 Si Σ = {a, b, c} entonces Σ2 = {aa, ab, ac, ba, bb, bc, ca, cb, cc}
Σn .

Ejercicio 2 Pruebe que Σ∗ =
n≥0

Σn .

Definimos Σ+ =
n≥1

Este es el conjunto de todas las palabras de longitud mayor que 1. Puesto que
ε nunca es elemento de nuestroalfabeto, es decir, ε ∈ Σ entonces Σ∗ = Σ+ y
/
Σ∗ = Σ+ ∪ {ε}
Definición 3 Para L un lenguaje se define de manera recursiva Ln así:
L0 = {ε}
Ln+1 = LLn
L∗ se define
Ln

L∗ =
n≥0
∗

L se denomina la Cerradura de Kleene o Cerradura estrella de L.
Ejemplo 3 Sea Σ = {0, 1} y L = {01, 1}, entonces
L3 = {010101, 01011, 01101, 0111, 10101, 1011, 1101, 111}

2.

Lenguajes y ExpresionesRegulares

En aritmética, usamos las operaciones + y × para construir expresiones tales
como
(4 + 1) × 5
De manera similar, usamos operaciones regulares para construir expresiones
que describen lenguajes, las cuales se denominan expresiones regulares. Un
ejemplo es:
(0 ∪ 1)0∗
El valor de la expresión aritmética es 25. El valor de una expresión regular es un
lenguaje. En este caso el lenguajeconsiste en todas las palabras que empiezan
con 1 o 0 seguido por cualquier número (finito) de 0 s. Otro ejemplo de una
expresión regular es
(0 ∪ 1)∗
Empieza con el lenguaje (0 ∪ 1) y se aplica la operación * . El valor de esta
expresión son todas las palabras posibles de 0 s y 1s.
Matemáticas Discreta

Prof. José Luis Chacón

Pensar y actuar

Trabajo VII

Semestre A2005

Teoría...