Automatas

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. El conjuntode 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 exactamente unacadena, 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 la palabra u. Dospalabras 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 se obtiene escribiendo las letras de u yluego 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 las potencias de Σ recursivamente de la siguientemanera: 1) 2) Σ1 = Σ Σ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} Ejercicio 2 Pruebe que Σ∗ =
n≥0

Σn .

Definimos Σ+ =
n≥1

Σn .

Este es el conjunto de todas las palabras de longitud mayor que 1. Puesto que ε nunca es elemento de nuestro alfabeto, 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 L∗ =
n≥0 ∗

Ln

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 Expresiones Regulares

En aritmética, usamos las operaciones + y × para construir expresionestales 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 lenguaje consiste 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

Lenguajes Regulares
Para un alfabeto Σ dado, los lenguajes regulares constituyen el menor...