CONJUNTOS REGULARES

Orlando Arboleda Molina

Escuela de Ingenierıa de Sistemas y Computacion deLa Universidad del Valle

19 de Octubre de 2008

Contenido

Conjunto regularesExpresiones regularesConjunto regularesTeorema de KleeneAutomatas que reconocen conjuntos regularesConjuntos regulares y Gramaticas regularesLimitaciones de los automatas de estado finito

Pregunta: Si los automatas de estado finito se pueden utilizarpara reconocer lenguajes. Que conjuntos pueden reconocer ?

Solucion: En 1956 el matematico estadounidense StephenKleene demostro que hay un automata de estado finito quereconoce un conjunto si y solo si, este conjunto se puedeconstruir a partir del conjunto vacıo, la cadena vacıa y cadenasde un sımbolo haciendo uso de los operadores de union,concatenacion y cierre de kleene, tomados en orden arbitrario.

Contenido

Conjunto regularesExpresiones regularesConjunto regularesTeorema de KleeneAutomatas que reconocen conjuntos regularesConjuntos regulares y Gramaticas regularesLimitaciones de los automatas de estado finito

Expresiones regulares

Las expresiones regulares sobre un conjunto I son definidasrecursivamente por:

◮ El sımbolo ∅ (conjunto vacıo) es una expresion regular◮ El sımbolo λ (conjunto {λ}) es una expresion regular◮ El sımbolo x (conjunto {x}) es una expresion regular

siempre que x ∈ I◮ Los sımbolos (AB), (A ∪ B), y A∗ son expresiones

regulares siempre que A y B son expresiones regulares

Cada expresion regular representa un conjunto.

Ejemplo: Las siguientes son expresiones regulares: (10)∗,(1 ∪ 0)∗, 0 ∪ (1∗ ∪ 0)∗

Contenido

Conjunto regularesExpresiones regularesConjunto regularesTeorema de KleeneAutomatas que reconocen conjuntos regularesConjuntos regulares y Gramaticas regularesLimitaciones de los automatas de estado finito

Conjunto regulares

Los conjuntos representados por expresiones regulares sonllamados conjuntos regulares.

Ejercicio1: Determinar las cadenas para cada uno de lossiguientes conjuntos regulares:

◮ 10∗

◮ (1 ∪ 01)(10)∗

◮ 0 ∪ 01◮ 0(0 ∪ 1)∗

◮ (0∗1)∗

Contenido

Conjunto regularesExpresiones regularesConjunto regularesTeorema de KleeneAutomatas que reconocen conjuntos regularesConjuntos regulares y Gramaticas regularesLimitaciones de los automatas de estado finito

Teorema de Kleene

Teorema 1 - Teorema de KleeneUn conjunto es regular si y solo si es reconocido por unautomata de estado finito.

Como construir los automatas que reconocen los conjuntosregulares ?

Contenido

Conjunto regularesExpresiones regularesConjunto regularesTeorema de KleeneAutomatas que reconocen conjuntos regularesConjuntos regulares y Gramaticas regularesLimitaciones de los automatas de estado finito

Automatas que reconocen conjuntos regulares

◮ Automatas que reconocen los conjuntos ∅, {λ} y {a}respectivamente

Automatas que reconocen conjuntos regulares (2)◮ Automata MAB que reconoce al conjunto AB

◮ Combina en serie a MA y MB

◮ SAB = SA⋃

SB

◮ Estado inicial sA

◮ FAB = FB. Anadiendo SAB si λ ∈ A⋂

B y FA si λ ∈ B◮ Transiciones: si λ ∈ A cada transicion que parta de SB y

desde cada estado previo a uno en FA ir hasta sB

Automatas que reconocen conjuntos regulares (3)◮ Automata que reconoce al conjunto A ∪ B

◮ Combina en paralelo a MA y MB

◮ SAS

B = SA⋃

SB⋃{sA∪B}

◮ Estado inicial {sA∪B}

◮ FAS

B = FA⋃

FB. Anadiendo sA∪B si λ ∈ A⋂

B◮ Transiciones: transiciones desde {sA∪B} con los simbolos

que procesaban sA y sB

Automatas que reconocen conjuntos regulares (4)◮ Automata que reconoce al conjunto A∗

◮ S∗

A = SA⋃{sA∗}

◮ Estado inicial {sA∗}

◮ F ∗

A = FA⋃{sA∗}.

◮ Transiciones: por cada transicion desde sA a un estado spara la entrada i , incluir transicion desde {sA∗} hasta s conel sımbolo i y una transicion desde cada estado final hastas para el mismo dato de entrada i .

Automatas que reconocen conjuntos regulares (5)

Ejercicios: Construir automatas de estado finito quereconozcan los siguientes conjuntos regulares:

◮ {11, 0}∗

◮ {11, 0}∗00, 1{10, 01}∗

◮ {11, 00}{01, 101}∗{1, 00, 10}∗

◮ {11, 00}{01, 101}∗{1, 00, 10}{1}∗

Contenido

Conjunto regularesExpresiones regularesConjunto regularesTeorema de KleeneAutomatas que reconocen conjuntos regularesConjuntos regulares y Gramaticas regularesLimitaciones de los automatas de estado finito

Conjuntos regulares y Gramaticas regulares

Teorema 2Un conjunto es generado por una gramatica regular si y solo sies un conjunto regular.

Ejercicio: Construir un automata de estado finito nodeterminista que reconozca el lenguaje generado por lagramatica regular G = (V , T , S, P), donde:V = {0, 1, A, S}T = {0, 1}P = {S → 1A, S → 0, S → λ, A → 0A, A → 1A, A → 1}.Nota: La idea es que el estado inicial es final si existe laproduccion S → λ. Adicionalmente que se cree un estado porcada sımbolo no terminal, mas un estado final adicional)

Conjuntos regulares y Gramaticas regulares (2)

Ejercicio: Hallar la gramatica regular que genere el conjuntoregular reconocido por el siguiente automata

Contenido

Conjunto regularesExpresiones regularesConjunto regularesTeorema de KleeneAutomatas que reconocen conjuntos regularesConjuntos regulares y Gramaticas regularesLimitaciones de los automatas de estado finito

Limitaciones de los automatas de estado finito

Ejercicio: Es el conjunto {0n1n | n = 0, 1, . . .} regular ?Nota: El conjunto puede ser generado con una gramatica librede contexto

Los automatas finitos:◮ Son limitados (capacidad de memorıa finita).◮ No reconocen lenguajes que no son regulares.

Modelos de computacion mas potentes:◮ Automata a pila (reconoce gramaticas libres del contexto).

No podrıa reconocer {0n1n2n | n = 0, 1, . . .}

◮ Maquinas de Turing ((reconoce gramaticas dependientesdel contexto).