3_lenguajesRegulares

Lenguajes Regulares

Departamento de Informática e Ingeniería de Sistemas
C.P.S. Universidad de Zaragoza

DIIS – Pedro J. Álvarez Pérez-Aradros y Rubén Béjar Hernández

Última revisión: Feb. 2003

LenguajesRegulares..ppt

27/03/2006

1

Índice
z

Problema de especificación de lenguajes

z

Lenguajes regulares

z

Expresiones regulares

DIIS – Pedro J. Álvarez Pérez-Aradros y Rubén BéjarHernández

LenguajesRegulares..ppt

27/03/2006

2

Especificación de lenguajes:
Introducción
z

Hasta ahora ha sido sencillo especificar qué
cadenas pertenecen a un determinado lenguajes
sobre algún alfabeto Σ.
Ldígitos = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0}

z

Objetivo:
Encontrar formalismos que me permitan
definir lenguajes más complejos.

z

¿Cuántos lenguajes diferentes puedo definir
sobre un determinadoalfabeto Σ?
† Cálculo

Σ*.

del número de palabras del lenguaje universal

† Cálculo

del número de subconjuntos, en este caso
sublenguajes, que puedo formar con las palabras del
lenguaje universal Σ*.

DIIS – Pedro J. Álvarez Pérez-Aradros y Rubén Béjar Hernández

LenguajesRegulares..ppt

27/03/2006

3

Especificación de lenguajes (II)
z

Teorema: Para todo Σ, Σ* es infinito
numerable.
†Consideremos

el alfabeto Σ = {a, b}

• Orden lexicográfico:
ε, a, b, aa, ab, ba, bb, aaa, ...
• Numeramos las palabras por orden
lexicográfico:
ε
0
a
1
b
2
aa
3
ab
4
ba
5
...
† Conclusión

(informal): dado que hemos
construído una función biyectiva de Σ* a N,
se tiene que Σ* es infinito numerable.

DIIS – Pedro J. Álvarez Pérez-Aradros y Rubén Béjar Hernández

LenguajesRegulares..ppt

27/03/2006

4Especificación de lenguajes (III)
z

Teorema: El conjunto de todos los lenguaje
sobre Σ no es numerable.
Demostración: Supongamos que el conjunto de
todos los lenguajes sobre Σ (L) es numerable. Si
es numerable L = {A0, A1, A2,...}
Como Σ* es numerable, Σ*={w0, w1, w2,...}
Sea B = {wi | wi ∉ Ai}, palabras que no
pertenecen al lenguaje con su mismo índice. B
es un lenguaje sobre Σ luego B = Ak paraalgún
k.
Si wk ∈ B, entonces wk ∉ Ak (= B), luego
wk ∉ B
Si wk ∉ B, entonces wk ∈ Ak (= B), luego
wk ∈ B.
Conclusión: La suposición de que el conjunto de
todos los lenguajes sobre Σ es numerable es
falsa. Luego el conjunto es no numerable.

DIIS – Pedro J. Álvarez Pérez-Aradros y Rubén Béjar Hernández

LenguajesRegulares..ppt

27/03/2006

5

Especificación de lenguajes:
Conclusiones
¿ Cuál es lamagnitud del problema de
especificar lenguajes sobre un Σ ?
¿ Existe algún método suficientemente
expresivo capaz de especificar todos los
lenguajes sobre un Σ ?
¿ Con qué método podemos especificar
todos esos lenguajes ?

DIIS – Pedro J. Álvarez Pérez-Aradros y Rubén Béjar Hernández

LenguajesRegulares..ppt

27/03/2006

6

Lenguajes regulares
z

Sea el alfabeto Σ. El conjunto de
lenguajesregulares se define de manera
recursiva como sigue:
1)

φ es un lenguaje regular.

2)

{ε} es un lenguaje regular.

3)

Para todo a ∈ Σ, {a} es un lenguaje regular.

4)

5)

Si A y B son lenguaje regulares, entonces
A∪B, A·B y A* son lenguajes regulares.
Ningún otro lenguaje sobre Σ es regular

DIIS – Pedro J. Álvarez Pérez-Aradros y Rubén Béjar Hernández

LenguajesRegulares..ppt

27/03/2006

7Lenguajes regulares: ejemplos.
z

Dado Σ = {a,b}, las siguientes
afirmaciones son ciertas:
φ y {ε} son lenguajes regulares
{a} y {b} son lenguajes regulares
{a, b} es un lenguaje regular
{ab} es un lenguaje regular
{a, ab, b} es un lenguaje regular
{ai | i ≥ 0} es un lenguaje regular
{aibj | i ≥ 0 y j ≥ 0} es un lenguaje regular
{(ab)i | i ≥ 0} es un lenguaje regular

DIIS – Pedro J. Álvarez Pérez-Aradrosy Rubén Béjar Hernández

LenguajesRegulares..ppt

27/03/2006

8

Lenguajes regulares: ejemplos (II)
z

Dado Σ = {a,b,c}, ¿El lenguaje de todas
las cadenas sobre el Σ que no contiene
ninguna subcadena ac es regular?
{c}, {a}, {b} son L.R. (3)
{c}* es un L.R. (4, *)
{b}{c}* es un L.R. (4, ·)
{a}∪{b}{c}* es un L.R. (4, ∪)
({a}∪{b}{c}*)* es un L.R. (4, *)
{c}*({a}∪{b}{c}*)* es un L.R. (4, ·)
¿Es...