automatas y lenguajes formales conceptos basicos

INTRODUCCION AL ESTUDIO DE LOS AUTOMATAS

CONCEPTOS BASICOS

Ing. Edecio R. Freitez

INTRODUCCIN

La presente unidad pretende ofrecer al estudiante unaserie de conceptos y ejemplos que permitan refrescar yafianzar diversos aspectos relacionados con la teora de lacomputacin, dado que la capacidad que el estudiante tengapara analizar y usar la notacin terica establecida,depender fundamentalmente del conocimiento de lasdefiniciones bsicas aqu presentadas.

En esta unidad se pretende dejar claro al estudiante laconceptualizacion de cada uno de los trminos empleados (smbolo, palabra, alfabeto, lenguaje), estableciendo la relacinexistente entre ellos y distinguiendo para cada casocaractersticas, propiedades y funciones que apoyan cada

concepto.

DEFINICIN DE TERMINOLOGA BSICA

Smbolo: Es una entidad abstracta que no definimos formalmente.

Es una representacin Grafica de un Concepto por algunasemejanza que el entendimiento percibe entre ambos; Puede sertambin definido, como un carcter o conjunto de caracteres,utilizados para representar una cantidad, operacin, instruccin, etc.

En su nocin ms primitiva, un smbolo es simplemente una representacin distinguible de cualquier informacin. Ejemplo: 1, 2; p, f; *, @; etc.

Palabra o Cadena: Representa una secuencia finita de smbolos.

Ejemplo: S 1,2,3; representan smbolos entonces:

w=12;

w1=231;w3= 222113, constituyen cadenas formadas a partir de

dichos smbolos


Longitud de una Palabra o Cadena: Si w es una cadena sobre cualquier alfabeto, La longitud de w esta conformada por l numero de smbolos que conforman dicha cadena.

Notacin: Si w es una cadena dada, la longitud de w se denota mediante el smbolo |w |.

Ejemplo: Sean las cadenas w1=12, w2=231 y w3=222113; se tiene:

l calcula de la longitud de cada palabra dada se determina de la siguiente

forma:

| w1 |= | 12 |=2.

| w1 |= |231 |=3.

| W1 | =| 222113 |=6.


Palabra o Cadena Vaca: Es una cadena que no contienesmbolos, es decir dicha cadena esta Constituida por cero (0)smbolos.

Notacin: La cadena vaca es denotada mediante lossiguientes smbolos:

por el smbolo .

Cabe destacar que puede convenirse cualquier otro smbolopara su representacin, pero en todo caso los smbolosanteriores son los ms usados.

Ejemplo: Sea W1= ; entonces w1= (Es la cadena opalabra vaca)

Nota: Dada que la cadena vaca no contiene smbolos setiene que la longitud de dicha cadena denotada por =0.

OPERACIONES CON CADENAS.

Concatenacin: Sean w1 y w2 dos cadenas respectivamente, laconcatenacin de w1 con w2 es la cadena que se obtiene al aadir a lacadena w1 la palabra w2, y se denota w1w2 o w1.w2

Ejemplo: sea w1 = pana y w2= dero la concatenacin de w1 con w2es la cadena w1.w2=w1.w2=panadero.

La longitud de w1w2=w1w2=w1+w2. En el caso de la cadenaanterior se tiene quepanadero=2.

Nota: La concatenacin de la palabra vaca con cualquier otrapalabra w, no modifica la palabra w, es decir, la cadena vaca secomporta como la identidad con respecto a la operacin deconcatenacin.


Potencia: la potencia i-esima para una palabra dada w, corresponde a laconcatenacin i veces de la palabra w con ella misma.

Sea w una palabra, para n se define:

, S n=0

Wn =

ww, s n>0

Ejemplo: Sea w = abc, una cadena entonces:

W0 =

W1 = abc

W2 = abcabc

W3 = abcabcabc

Y as sucesivamente, se dice que wi es la potencia i-esima de W.


Reflexin: Sea la palabra w =X1, X2,..., Xn se tiene que lacadena inversa de w denotada

por: Wi, se forma invirtiendo el orden de los smbolos en lapalabra w; wI =Xn,..., X2, X1.

Nota: Para cualquier cadena w, se tiene que s w=,

|wI =w.

Ejemplo:Sean los smbolos {1,2,3}; {a, b, c}: Dos cadenasasociadas a los Conjuntos de smbolos dados serian: w1=122;w2=abca; respectivamente, para. Las cadenas w1 y w2, setiene que:


Alfabeto: Es un conjunto no vaci y finito de smbolos.

Ejemplo:

- El Alfabeto ingles.

- El Alfabeto Espaol

- El Alfabeto Griego.

Alfabeto : Es un conjunto finito y no vaco de smbolos(letras,nmeros, Combinaciones de letras y nmeros,... Si es unalfabeto, , denota que es un smbolo de .

Ejemplo: Sean los alfabetos dados por:

=0,1,2,3,4,5,6,7,8,9; entonces 3.

1=ma, pa, ta ,la, entonces pa1.

Universo de un Alfabeto : Todas las palabras que se puedenformar con los smbolos del alfabeto . Contiene un numeroinfinito de elementos.


Notacin: El universo de un alfabeto puede denotarsemediante el smbolo: * o W()

Ejemplo: para los alfabetos: y 1 del ejemplo anterior, setiene que l universo asociado en caso ser:

W()={,0,1,2,3,4,5,6,7,8,9,01,02,03,04,05,06,07,08,09,010,... }

W()={,ma,pa,ta,la,mapa,mata,mala,mamapa,mamapa,.}


Lenguaje: Es un conjunto de palabras. Estos pueden ser bastantegrandes, pueden ser infinitos aunque cada cadena del mismo tenga lalongitud finita.

Tipos de Lenguajes:

Lenguaje Formal o Artificial: Este tipo de lenguaje atiende a reglaspreviamente establecidas;; por tal razn se ajustan a dichas reglas, noevolucionan y se crean con un propsito especifico. Un ejemplo de estoslenguajes lo constituyen los lenguajes de programacin.

Lenguaje Natural: Surgen de la necesidad de comunicacin existentesentre los seres humanos, las reglas gramaticales que rigen la estructurade estos lenguajes han sido desarrolladas con posterioridad paraexplicacin de las mismas. Como ejemplo de estos lenguajes se puedenmencionar el espaol, el ingles, y el francs entre otros.


Lenguaje sobre un alfabeto : Viene dado por todosubconjunto de palabras del universo asociado alalfabeto . Se denota como L().

Nota: Dado que el universo asociado a un alfabeto esinfinito, existen infinitos lenguajes para dichoalfabeto.

Ejemplo: Sea 1={ma, ta, la, pa}; se tiene que:

W(1)={, ma, ta, la, pa, mata, mala, mapa,...}

L1(1)={, ma, ta, la}

L2(1)={ ma, ta, la, mata, mala}

OPERACIONES CON LENGUAJES

Unin: sean L1 y L2 dos lenguajes, su unin denotada por L1UL2contendr todas las palabras que pertenezcan a cualquiera de los doslenguajes, es decir:

L1UL2 ={x / xL1 o xL2 }

Ejemplo: tomando como referencia el ejemplo anterior se tiene que:

L1UL2={, ma, ta, la, mata, mala}

Interseccin: Si L1 y L2 son lenguajes, su interseccin denotada por L1L2contendr todas las palabras que pertenezcan a los dos lenguajes, esdecir:

L1L2 ={x/ x L1 y xL2}

Ejemplo: Tomando L1 y L2 del ejemplo anterior se tiene que:

L1L2 ={ma, ta, la}


Resta: Si L1 y L2 son lenguajes, la resta de L1 y L2 denotada por L1 - L2contendr todas las palabras que pertenezcan a L1 y no pertenezcan a L2,es decir:

L1 - L2={x/ xL1 y xL2}

Ejemplo: Para L1 y L2 del caso anterior se tiene que:

L1-L2={}

L2-L1={mata, mala}

Concatenacin: Dados dos lenguajes L1 y L2, su concatenacin, denotadapor

L1. L2, contendr todas las palabras que se pueden formar por laconcatenacin de la palabra de L1 y otra de L2, es decis:

L1L2={xy/ xL1 y yL2}

Ejemplo: Para L1 y L2 del ejemplo dado se tiene que:

L1L2={ ma, ta, la, mama, mata, mala. mamata, mamala... }


Potencia: la potencia i-esima de un lenguaje corresponde a laconcatenacin i veces del lenguaje con el mismo.Ejemplo: Sea ={a,b}, L()={a,b} entonces:

L2 =aa ,ab, ba, bb Nota: Por definicin se tiene que para todo lenguaje Li, se cumple que:

L0 =. Clausura Positiva: se forma por la unin de todas las potencias del lenguaje

excluyendo la potencia cero, se denota por: L+ Ejemplo: Para L()={a,b}, se tiene que:

L()+ ={a, b, aa, ab, ba, bb, aaa, aab,...} Iteracin, Cierre o Clausura: El cierre de un lenguaje se forma por la unin

de la palabra vaca a la clausura positiva de un lenguaje, se denota por:L* = L+ U

Ejemplo: Para L()=a,b, se tiene que:

L()* =a, b, aa, ab, ba, bb, aaa, aab,...


Reflexin: La reflexin de un lenguaje L viene dada por laaplicacin de la reflexin a cada una de las palabras queconforman el lenguaje L; L-1 = x-1 / xL

Ejemplo: Sea a, b, se tiene que L1a, b, aa, ab, ba,bb, aaa, se tiene que:

L-1 = {a, b, aa, ba, ab, bb,, aaa}

Lenguajes regulares(LR).

Definicin: Los lenguajes regulares sobre un alfabeto dado, son todos los lenguajes que se pueden formar a partirde los lenguajes bsicos , {}, {a}, a, por medio de lasoperaciones de unin, concatenacin y estrella de Kleene.

LENGUAJES REGULARES

Sea un alfabeto. Se definira recursivamente el conjunto de los lenguajes

regulares asociados a , como muestra a continuacin:

- , representa un lenguaje regular.

{}, representa un lenguaje regular.

Para todo a,, {a}, representa un lenguaje regular.

Si A y B son lenguajes regulares sobre , tambin lo son:

A U B (unin)

A B (concatenacin)

A*(estrella de Kleene)

Ningun otro lenguaje sobre , es regular.

Nota: Cabe resaltar que los apartados a-, b-, y c-, se consideran

lenguajes regulares bsicos.

LENGUAJES REGULARES

Ejemplo: Sea {a, b. Los siguientes son lenguajes regulares sobre .

- , representa un lenguaje regular.

- {}, representa un lenguaje regular.

- Para todo a,b,, {a}, b representan lenguajes regularessobre

- El lenguaje A de todas las palabras que tienen exactamente una a:

A =b*. {a}. {b*

- El lenguaje B de todas las palabras que comienzan con b:

B = {b}. {a, b*

- El lenguaje C de todas las palabras que contienen la cadena ba:C = {a, b* {ba} {a, b*

EXPRESIONES REGULARES (ER).

Expresiones Regulares (ER).

Definicin: Las expresiones regulares representan lenguajesregulares y su propsito es simplificar la escritura de los lenguajesregulares. Recursivamente una expresin regular sobre un alfabeto dado se define como:

Expresiones Regulares bsicas:

- es una expresin regular que representa al lenguaje .

- es una expresin regular que representa al lenguaje {.

- a es una expresin regular que representa al lenguaje {a},a.

Si R y S son expresiones regulares sobre tambin lo son:

- R.S (Concatenacin.).

- R U S(Unin.)

- R* (Clausura de Kleene representado por el lenguaje R).


Ejemplo: Dado el alfabeto ={a, b, c}, se tiene que:(a Ub*)a*(bc)* es una expresin regular que representa allenguaje: ({a}U{b}*).{a}*{bc}*).

Nota:Es importante destacar que toda expresin regular sobre, denota un lenguaje regular sobre .

Ejemplo: A continuacin se presentan dos ejemplos deexpresiones regulares.

- ab1 Representa el lenguaje formado por palabras o cadenasque empiezan en a seguida de ninguna una o mas bes.

- (aUb)* Representa una palabra formada por por a, b o mascaracteres que puedan ser ser a o b.


Lenguaje Representado por una Expresin Regular (ER): Se puede definirrecursivamente un lenguaje regular L, por medio de una expresin regularhaciendo uso de las siguientes reglas de calculo.

- Si = entonces L=.- Si = entonces L=.- Si = a, a, entonces L=a.- Si y son ER, entonces L =L U L.- Si y son ER, entonces L .=L . L.- Si es ER, entonces L(1) =L()1- Si es ER, entonces L(())=L().

Ejemplo: Para la expresin regular ab1 se tiene que el lenguaje regular asociado es: L(ab1) =L(a)L(-ab1) =L(b)1=

EL TEOREMA DE KLEENE

Teorema de Kleene

Estos teoremas permiten demostrar lasequivalencias entre las Expresiones Regulares y losAutmatas Finitos, en cuanto a que ambosrepresentan de una u otra Forma, lenguajesregulares. Los teoremas son los siguientes:

Teorema de Anlisis: El cual expresa que todoLenguaje aceptado por un Autmata Finito esRegular.

Teorema de Sntesis: El expresa que todo lenguajeregular es aceptado por un Autmata Finito.

GRACIAS POR SU ATENCION

automatas y lenguajes formales conceptos basicos

Documents