Centro Universitario de Monterrey A. C.

Carrera:

Informática

Semestre:

5to. Semestre

Materia:

Teoría de la Computación

Trabajo:

Apuntes del semestre

Maestro:

Ing. Miguel Angel de la Torre

Alumno:

Victor Iván Robles Martínez

TEORÍA DE LA COMPUTACIÓN

TEMARIO

I Gramáticas y Lenguajes Formales.

II. Máquinas de Estado Finito.

III Autómatas de Estado Finito.

IV Autómatas de Pila.

V Máquinas de Turing.

VI Computabilidad.

OBJETIVOS DEL CURSO:

1° Obtener los conocimientos preliminares necesarios para el desarrollo de las etapas de análisis de un Compilador.

2° Implementar modelos matemáticos a partir de algunos sistemas reales de tipo electrónico o computacional principalmente-

3° Profundizar en el conocimiento sobre la computabilidad de los algoritmos.

EVALUACIÓN

Primer Examen Parcial 25 %

Segundo Examen Parcial 25 %

Proyecto Software 25 %

Tareas 10 %

Proyecto Terminal 15 %

TOTAL 100%

BIBLIOGRAFÍA

1.- Teoría dé Autómatas y Lenguajes Formales.

Deán Kelley.

Editorial Preníice Hall.

2.- Introducción a la Teoría de Autómatas, Lenguajes y Computación.

John E. Hopcroft / Jeffrey D. Ullman.

Editorial CECSA.

3.- Teoría de la Computacion

J. Glenn Brookshear.

Editorial Addison Wesley Iberoamericana.

BIBLIOGRAFÍA DE APOYO:

1 Ejemplo: Aho / Sethi / Ullman. (Editorial Addison Wesley).

2.- Libros sobre Matemáticas Discretas.

Ejemplo; Johnsonbaugh. (Editorial Iberoamericana).

3.- Libros sobre Lenguajes de Programación.

Ejemplo; Sethi. (Editorial Addison Wesley).- Libros sobre Compiladores.

MÓDULO I

GRAMÁTICAS Y LENGUAJES FORMALES

CONCEPTOS GENERALES

-TEORÍA DE LOS LENGUAJES FORMALES: Estudio de los Lenguajes Formales.

Una rama importante de esta teoría se ocupa de la descripción finita de Lenguajes Infinitas. Esta representación adopta la forma de un mecanismo abstracto para generar o reconocer cualquier cadena del Lenguaje. Esta rama se adapta a la sintaxis de los lenguajes de programación (en cuanto son distintos de su semántica, que requiere elementos de trabajo bastante diferentes). Así, el conjunto de todos los programas válidos de Pascal o de C, puede considerarse como un Lenguaje Formal sobre el alfabeto de símbolos de Pascal, o de C.

Las Gramáticas proporcionan una base para, describir sintaxis, en tanto que los Autómatas de Pila sirven de base para el diseño de tos programas de análisis sintáctico. Por otra parte, el deseo de formalizar, los lenguajes reales que llevo a Niuman Chomsky a la iniciación de este tema en 1956.

GRAMÁTICA FORMAL: Es un esquema general para la. representación finita de los lenguajes, es decir, un soto modelo dinámico para generar asî frases 0 cadenas de un lenguaje.

GRAMÁTICA FORMAL: Es una de las maneras principales de especificar un lenguaje formal aunque sea infinito por medios finitos. Los lenguajes pueden ser finitos o infinitos.

LENGUAJE FORMAL: Lenguaje con reglas explícitas para su sintaxis y semántica. Como ejemplo se pueden citar los lenguajes de programación y también lógica como el cálculo de predicados. Así, los Lenguajes Formales se distinguen de los naturales tales como el castellano, cuyas reglas a medida que evolucionan con el uso de ser una norma completa o precisa de la sintaxis del lenguaje y mucho menos de su semántica.

Conceptos iniciales básicos:

LENGUAJE FORMAL: Conjunto de palabras formadas por ciertas reglas.

GRAMÁTICA FORMAL: Reglas para formar las palabras del lenguaje.

Todo Lenguaje Formal, siempre estará relacionado a una Gramática Formal que especifica el mecanismo de producción de las cadenas que lo conforman.

LENGUAJE FORMAL: Sea un conjunto finito de elementos llamado alfabetico, un lenguaje formal L definido sobre £ es un subconjunto de £* (el conjunto de todos los arreglos o cadenas posibles de formar con los elementos de £).

Ejemplos de Alfabetos:

E = { a, b, c, ch, d, e, f. g, h, etc.} En idioma castellano.

E = { .-,-...,-.-.,----,-..,.,..-.,....,..,etc.} En código Morse.

E ={.,-} En código Morse.

E = {x | x es un carácter del código ASCII}

E ={0, 1,2. 3.4, 5,6, 7,8,9}

E = {+,-,',/}

E = { a, e, i, o, u}

EJEMPLO:

Diseñar un Lenguaje Formal cualquiera, a partir de ciertas reglas expresadas textualmente y con el alfabeto £ = {x, y, z}.

zn = {s | s es toda cadena de longitud n que se pueda formar con los símbolos de I,}

¡f r=u} ^.^ .

| ^= i-íx.y.z}

S, í:2 = {xx, xy, xz, yx. yy, yz, zx, zy, zz}

^ 1¡3 = {xxx. xxy, xxz, xyx, xyy, xyz, xzx, xzy, xzz, yxx, yxy. yxz, ... , zzy, zzz}

U Z4 = {xxxx, xxxy, xxxz, xxyx, xxyy, xxyz, xxzx, xxzy, xxzz, ... , zzzy, 7772 }

^ £* == U Sn n e No, es decir. I* = Z° U £1 U X2 U Z3 U ...

I; £* se llama conjunto de todas las palabras sobre S.

j^. ' t:."'-^ -'^''^F I- f-~i^----t.--/ i;;.í ' <. ^

I r = Ü Sn n e N, es decir, S' = I;1 U Z2 U I3 U £4 U ...

í £+ se llama conjunto de todas las palabras no yacías sobre Z.

^ La forma de relacionar los dos conjuntos es: E* = S7 U { ?. }.&'

II Determinar el Lenguaje Formal, si las reglas gramaticales (en forma textual) fuesen:

La cadena es de longitud menor o igual a tres.

" La cadena finaliza con x o con z.

a La cadena no inicia con y.

i >. i '''

L = { x, z, xx, xz, zx, zz. xxx, xxz, xyx, xyz, xzx, xzz. zxx, zxz, zyx, zyz, zzx. zzz}.

Con otras reglas gramaticales, el Lenguaje pudiera ser:

L = {^, x. xy, yx, xz, zz, xyz, yyz, zxx, xxxx, ...}

Conceptos:

Los elementos a,e £ sfi llaman Símbolos de Y^_. ' •\(^-r\<

Los elementos arman, palabras cadenas y arreglos sobre La longitud de una cadena se expresa como. y consiste en la cantidad de símbolos cadena de longitud cero se llama cadena vacía y se representa: ^. ,,A, e- Es el elemento neutro en aritmética de cadenas.

Los Lenguajes Formales se comportan siempre en la forma más parecida posible a los naturales, al tratar de ser un modelo de éstos.

Nomenclaturapara cadenas:

xxxyyzxxzzz = 'x^zx^3,

xyzyzyzyyyx =- xyízy)3^ = x(yz)3y3x,

a^bü^...^ z°-^

El orden en el que aparecen los símbolos sí es aportante. Por ejemplo ab ^ ba.

"K - ri^'^ \iA \ ^\, c.

CONCEPTO: Sea S == una cadena cualquiera, entonces:

a) u es llamado prefijo. >

b) v es llamado infijo. >

c) w es llamado sufijo, y

Aplicado a un ejemplo;

Sea S = COSMOS

Prefijo: ?i, C, CO. COS, COSM, COSMO, COSMOS

Sufijo; ?i, S, OS, MOS. SMOS, OSMOS, COSMOS

Infijo; Á, C.O.S,M,CO, OS, SM, MO, OS, COS, OSM, SMO, MOS, COSM, OSMO,

SMOS, COSMO, OSMOS. COSMOS.

CONCATENACIÓN DE CADENAS , , , ^

Si ,U ^ UiU2Ua... U,n , U*V=UV= ,Ui U2 ... Um,yi ^2 ,-.- Vn

V= ViV2V3.-. Vn i ^ v

Por ejemplo: u = corcho, v = lata, uv = corcholata.

Las cadenas a concatenar pertenecerán al mismo conjunto £*.

OPERACIONES SOBRE LENGUAJES

Puesto que los lenguajes formales son conjuntos, se les pueden aplicar todas las operaciones de los mismos, sin embargo solamente son de-, utilidad para casos.

prácticos la union y la concatenación.

L u M == { s | S e L ^ S e M } > Jr c r

L"M= LM={lm|leL,meM} " r ^ ^r^,^, ,n

EJEMPLO:

Sean Li = { Á, a, ac, bca }, L2 = { ^-. b, cb, ab }, evaluar:

a) Li U L2 == { ^, a. ac, bca, b, cb, ab }

b) Li • LS = { ^, b, cb, ab, a afe, acl?, aab, ac, acb, accb, acab, bca, bcab,

^l^1^- bcacb.bcaab^ ('1^^ ,,. .vi";

{\] sin-0 ')

Ln = • Ya que se traía de una R- de Recurrencia.

EJEMPLO:

Dado L = { a, ac, ba, cba }, evaluar Lo, L1, L2 y L3.

Lo- U}

L1^ L.LÜ^ L={a.ac, ba, cba }

L2^ L" L1 = {.aa, aac, aba, acba, acá, acac, acba, accba, baa, baac, baba,

bacba, cbaa, cbaac, cbaba,cbacba }

Q -']

L = L* L ={ aaa, aaac, aaba. aacba, aaca, aacac, aacba...

acaa, acaac, acaba,acacha, acaca, acacac,...

baaa, baaac, baaba, baacba, baaca, baacac...

cbaaa,cbaaac, cbaaba, cbaacba. cbaaca,...}

L* = U L" | n É¿ No = Lo U L1 U L2 U ... se le llama Cerradura-de-K4eene de L;

L^ULn |n eN= L1 U i-^U L3 U ... se le llama Cerradura Positivaide L.

LA ==L' si A. e L. Z=U,...}

L* ^L/Up.} si A. ^ L,L={^ ...}

GRAMÁTICA FORMAL

También se conoce como Sistema de estructuracion que difiera en el siguiente cuarteto ordenado:

1) 1) Un conjunto finito "N" de símbolos

2) Un conjunto finito "T" de símbolos terminaciones. en donde N n T= 0

3) Un subconjunto finito ilP" de ((N uT)* - TA ) X (N uT)* llamado conjunto de configuraciones o reglas de producción.

4) Un símbolo inicial Go e N.

Se expresa en forma sintética como G == (N, T, P^ oo). Es muy importante aclarar que esta nomenclatura, al igual que en algunos otros casos de los temas tratados en este curso, se pueden tener algunas diferencias según el autor de la referencia que se consulta.

E! conjunto P es el más importante en la definición de una Gramática.

EJEMPLO:

Diseñar una Gramática Forma) cualquiera y determinar alguna cadena del Lenguaje que genera:

G=(N,T,P,ao)

N== {A,B,C,D} T= {0,1 } - <TO={A}

P= {A->ODA, A^BD1, A^CO, '^ ,,

B->1C1, B ^11, i1 ^

C-^10A1, C-^010, C1 -^A,

D-^CO, D-^1, D1->C}

Se acostumbra utilizar las letras mayúsculas para designar los no terminales. Los terminales son aquellos

Una cadena s e L(G) sería:

A-s> ODA=>01A^. 01CO.^> 010100 , que es lo mismo que (01)2 O2

En este caso se cuenta con ,toda una serie de composiciones (que consisten en posibles sustituciones de una subcadenas por otra) en el conjunto P, disponibles para

utilizarse en el orden que se desee, y las veces que se requieran.

Las composiciones no son substituciones bidireccíonales.

N uT =-> Alfabeto de la Gramática : ZG.

T => Alfabeto de el Lenguaje : SL

-^ Las reglas de producción deberán:

a) Estar formadas exclusivamente con elementos de N uT

b) Tener en .§y lado izquierdo aj menos yn_símbQ!aJiQjemiioaL.

EJEMPLO:

Explicar por qué razón en la definición del diseño de las composiciones se dice que éstas son de la forma ((N uT)* - T ) X (N uT)*.

N= {X,Y,Z} T= {a,b} N uT = { X, Y, Z, a. b} ^QT^

(N uT)*: A, XY, abb. bZX, ZaY, aYZb, aabba. ... (posible lado derecho)

T*: ^, a, b, aa, ab, ba, bb, aaa, aab, ..., bbb, ... C^Üti^ - T^

(N u T)* - T* == XY, bZX, ZaY, aYZb,... (posible lado izquierdo)

NOTA: (N uT)* - T* contiene las cadenas formadas con los elementos de N uT pero conteniendo al menos un elemento de N.

GRAMÁTICA MAL ESTRUCTURADA

En ocasiones, las reglas de producción para una Gramática Forma! se diseñan con ciertos "errores de Lógica".

EJEMPLO:

Describir los errores que hacen de la siguiente una Gramática mal estructurada.

G=(N,T,P,oo)

N= {A.B.C.D} T= {0,1} oo={A}

P= {A->B1. A-^BC, AC-^CA, C-> CA, DA->01, D->Á.}

* No existe regla alguna que especifique lo que produce B.

* Ninguna regla produce D.

* Verificar que no haya reglas inútiles (nunca utilizadas), como es el caso de la combinación DA, que nunca se presentará al derivar

Se recomienda que todo símbolo no terminal aparezca por lo menos una vez en cada lado. de al menos una regla de producción (y en composiciones distintas), con

excepcion del símbolo inicial que puede no aparecer al lado derecho.

DEIRIVACION

Es la acción de sustituir en una palabra no terminal, partiendo del símbolo inicial y hasta llegar a una cadena con terminales solamente, una subcadena por su

equivalente según las reglas de producción; se expresa: A => B.

COMPOSICIÓN O REGLA DE PRODUCCIÓN

Se expresa como A -> B, donde A e [N uTJ* - T y B e (N__uT)*, y en ellas se Especifica que tiene que se puede sustituir al construir una cadena.

CARACTERIZACIÓN DE UNA GRAMÁTICA

Consiste en expresar las características de producción de una Gramática presentemente por medio de una expresión algebraica, o bien, por medio de enunciados si lo anterior no es posible. No existen métodos generales para caracterizar los Lenguajes pero se debe tener en cuenta el orden en el que se aplicarían las composiciones si es que van a ser usadas.

EJEMPLO:

Caracterizar la Gramática G = ({R, S}, {a, b}, {R ^ bR, R -> aS, S ^ bS, S -> b} ,

{R}) \

R --> bR

bbR

bbbR

La caracterización sirve para expresar las características que tienen 3 cadenas de üri-Lenguaje Formal. A partir de ella se pueden deducir innumerables cadenas, así

descubrir simple vista si una cadena pertenece a si mismo Por ejemplo: Las cadenas originadas pc"Na Gramática anterior tienen una sola a y terminan en b, por to que:

b^b8 e L(G)- ab8 e L(G) bWa ^ L(G) b(r)a ^ L(G)

EJEMPLO PROPUESTO:

Diseñar la Gramática que produce L(G) = { On1n | n e N }. ¿Y sí L(G)

No?.¿YsiL(G)=={Om1n|m,neNo}?.

{OfT | n e

Una Gramática genera en la mayoría de los casos un Lenguaje, con un número infinito de cadenas pero todas ellas de la misma estructura gramatical

Dada una Gramática G puede construirse un Lenguaje L(G), utilizando composiciones para derivar en las cadenas que constituyen el Lenguaje

L(G)={s s eT* A oo"=>s}

GRAMÁTICAS EQUIVALENTES: n

Dos gramaticas Gi Y G2 se llaman equivalentes, en símbolos Gi - G2, sl.L(£i} =

.LíGá. S* dos Gramáticas son equivalentes, entonces tendrán los mismos símbolos terminales y muchos problemas el mismo símbolo inicial Sin embargo, las

composiciones serían diferentes, y muy posiblemente, también el conjunto de los símbolos no terminales.

Se deja al alumno proponer ejemplos de Gramáticas equivalentes.

Nótese como, si bien una Gramática debe producir un solo Lenguaje, un Lenguaje puede ser generado por distintas Gramáticas. Esta afirmación concuerda con el

concepto de función, recordando que L == f (G).

FORMA NORMAL DE BACKUS (BNF)

Fue la primera notación formal cuyo empleo se ha generalizado para describir la sintaxis dé un lenguaje de fomación, Ja creó John Backus_en 1960. Algunos

lenguaJesdé a\ia nivel como Fortran, Pascal yAIgol pueden representarse en BNF.

La notación se adoptó de inmediato para describir Algo! 60. Después se supo que Panini había usado una notación similar a la BNF entre 400 y 200 A.C. para describir

las complejas reglas de la Gramática del sánscrito.

Las siglas BNF comenzaron como abreviatura de Backus Normal Form, y después

se transformo su interpretación en Backus - Naur 1-orm para reconocer contribuciones de este último como editor del informe de ALGOL 60. Unavariante surgida posteriormente fue la BNF extendida. Estas son representaciones. En combinación conlos-iliagramas o esquemas de :sintaxis (que son en sí reglas de producción en modo gráfico), pueden utilizarse para expresar de forma como seconstruyen los programas en un Lenguaje de programación de alto nivel.

Backus -l Naur Form

CAMBIO DE NOMENCLATURA

' Símbolos no terminales: <A>

-Composiciones; A ::^B

' Composiciones múltiples: A::^B |C | D | ... | L

i I . , 1

EJEMPLO:

Transformar la' siguiente Gramática a la BNF correspondiente.

G = ({R, S}. {a, b}. {R -^ bR, R -> aS, S -. bS, S -> b}, {R})

G=({<R>, <S>},{a, b},{<R> ::= b<R> | a<S>, <S> ::== b<S> | b}, {<R>})

En el ejemplo; anterior se empleó para fines didácticos la conversión a la notación de BNF de una Gramática simple, siendo ésto inadecuado. En realidad se la debe

utilizar en casos en los que para nombrar a los símbolos no terminales se deba emplear más de un solo carácter (no confundir símbolo con carácter).

EJEMPLO:

Mostrar que s=-318 e L(G), donde G = ( N, T, P, ao)

N = { <entero>. <entero c/signo>, <entero s/signo>, <dígito> }

{+,-,0,1,2,3.4,5,6,7,8,9}

P= í

<entero s/signo>,

•<eníero s/signo>;

<dígito> ::0/1/2/3/4/5/6/7/8/9)

GO = { <entero> } (Es lo que produce la Gramática),

NOTA: Existen otras Gramáticas equivalentes a la anterior para el mismo fin.

-<d¡Qito><dÍQ¡to><entero s/signo> -> -<díQito><dígito><dígÍto&> =>

-3<dígÍtQ><dígito> •=> -31<dÍQito> =>-318

La Gramática genera todos los números enteros válidos y nada más. Por tanto produce, por ejemplo 1649, -65, +1000000, etc. pero no-36.2. ni 12., ni 67+.

EJEMPLO: , i ^

¿De qué frases consta la siguiente Gramática? \ • ^' \ •' i ' 'l ")

P = { <frase> ;:== <sujeto> <predicado><punto>.

<sujeto> ::^<sustantivo>,

<predícado> ::= <verbo intransitivo> | <verbo transitivo> <objeto>,

<punto> ::= . ,

<sustantivo> :;- Rubén | Sandra,

<verbo trans¡tivo> '.:=- odia | golpea, • •

<verbo Íntransitivo> :;= duerme,

<objeto> :;= a <sustantivo>} i i

Respuesta:

Rubén odia a Rubén.

Rubén golpea a Rubén.

Sandra odia a Rubén.

Sandra golpea a Rubén

Rubén duerme.

Rubén odia a Sandra-

Rubén golpea a Sandra.

Sandra odia a Sandra.

Sandra golpea a Sandra.

Sandra duerme.

Aún los Lenguajes Formales finitos, tienen una Gramática Formal que los produce. En el Procesamiento de los Lenguajes Naturales, área de la Inteligencia Artificial, se

emplea la Teoría de los Lenguajes Formales para su diseño. Investigúese sobre el trabajo desarrollado por Noam Chomsky para establecer sus primeras bases.

EJEMPLOS DE ALGUNAS REGLAS DE PRODUCCIÓN DE

TURBO PASCAL EXPRESADAS EN BNF

<ASIGNAClÓN> ::^ <IDENTIFICADOR> :- <£XPRESIÓN>

< SENTENCIA COMPUESTA> ::- BEGIN <SENTENClAS> END

<SELECTIVA DOBLE> ;:= IF <CONDICIÓN> TH£N <SENTENCIA> ELSE <SENTENCIA>;

<SELECTIVA MÚLTIPL£> ::= CASE <SELECTOR> OF

<L1STA DE CONSTANTES^ <SENTENCIAS 1>;

<LISTA DE CONSTANTES> : <SENTENC1AS 2>;

[ELSE <SENTENC1A POR DEFECTO> ]

! END;

<MIENTRAS> ::= WH1LE <CONDIC1ÓN> DO <SENTENCIA> ;

<REPETIR> ;:=- REPEAT <SENTENCiA> UNT1L <CONDIC1ÓN>

<FUNC)ÓN> ::= FUNCTION <IDENTIFICADOR> (<PARÁMETROS FORMALES>) : <T1PO>;

De la misma manera cada Lenguaje de Programación tiene su colección de reglas de producción que definen su sintaxis. Esta colección de composiciones son el punto de

partida para el diseño de un compilador de acuerdo a las especificaciones deseadas. También se pueden emplear eficazmente para comprender programas escritos en

Lenguajes no conocidos por el estudiante y para comparar Lenguajes de Programación.

TAREA PARA EL ESTUDIANTE:

Investigar en algún texto sobre un lenguaje de programación típico, cómo se expresan sus reglas sintácticas, ya sea en BNF, BNFE o en diagramas de sintaxis, además de comprender cómo se pueden transformar éstas entre sí.

JERARQUÍA DE CHOMSKY

Es una clasificación de cuatro clases de Lenguajes Formales cuya definición, realizada por Noam Chomsky en 1959, marcó el comienzo de esta teoría. Estas clases de Lenguajes se denominan tipo O, 1, 2 y 3, siendo cada una de ellas un subconjunto de la anterior. Cada tipo puede definirse por una clase de Gramática o Lenguaje, o por una clase de Autómata, como se indica en la tabla.

GRAMÁTICA DE CHOMSKY (TIPO 0)

No existen restricciones-en las reglas de producción, excepto que cumplan con las características para tener sus composiciones elaboradas en forma correcta.

EJEMPLO:

Diseñar una Gramática de Chomsky cualquiera.

G=(N,T,P,oo)

N={A.B,C,D} T={0,1,2} , GO={A}

P={A->B02 D01 0. AB->BA D. C -> OA 1B2A 1

D->AO B02 2 \, OB->A, B-> CA} -\

GRAMÁTICA SENSIBLE AL CONTEXTO (TIPO 1)

Toda composición es de la formal a A p -> u 5 pj donde: a, p e (N uT)*; A e N; 5 e (N u T)^ Se interpreta como que el prefijo derecho sea igual que el izquierdo, que el

sufijo derecho sea igual que el izquierdo, que el infijo izquierdo sea un no terminal, y que el infijo derecho sea cualquier cosa con excepción de Á..

EJEMPLO:

Diseñar una Gramática Sensible al Contexto cualquiera.

G=(N,T,P,<7o),

N= {S,A, B.C, D, E} T= {a, b,c}

oo = { S }

P = { S -> aAB

B -> De,

CD -^ CE

DE -> De,

aB,

r\ -7 d/AV_/

D -> b,

CE ^ DE

Ce -> Dcc}

aC,

Obtener una cadena s e L(G) y demostrar que en muchos casos no es muy recomendable trabajar con este tipo de Gramáticas debido a la ¡ndecibilidad

S => aAB r^> aaACB => aaACDc => aaACbc =^ aaaCCbc => ?

L(G) = { ambnc[n | m, n e N}, el cual es un Lenguaje sensible al contexto.

Dado que | a A p | ^ | a ó P . una característica de las derivaciones en una Gramática sensible al contexto, es que la longitud de la cadena nunca se decrementa al derivar.

GRAMÁTICA LIBRE O INDEPENDIENTE DE CONTEXTO

(TIPO 2)

Sí toda derivación es de la forma A -"> 6 donde A e N y ó e (N UTT; el lado izquierdo de las composiciones es un solo símbolo no terminal y el derecho no

deberá ser ^.

EJEMPLO:

Diseñar una Gramática Libre de Contexto cualquiera:

G-(N,T,P,cyü)

N- {E,F,G,H} T= {q,r,s} go={E}

P ^ {E->FGs rE GF

F ->Hq r,

G -^ Ers Fq SE

H->GEs sG q}

En una Gramática de este tipo nunca se presenta el caso de una derivación que no se pueda concluir.

GRAMÁTICA REGULAR (TIPO 3)

Si toda composición es de una de las formas A -> a p bien A -> a B donde A, B e N y a e T. Al derivar una cadena aparece un solo símbolo no terminal a la vez; la

cadena se va formando símbolo a símbolo de izquierda a derecha.

Algunos autores consideran como Gramática Lineal a la que cada producción contiene a lo sumo, un no terminal en el lado derecho de las reglas. Esta es lineal

derecha si un no terminal puede aparecer, únicamente, como su símbolo extremo derecho, es decir si cada producción tiene una de las formas A -xo o A -> ü)B,

donde A. B son no terminales y co es una cadena de termínales. Una Gramática lineal izquierda puede definirse como la que contiene reglas A -HO o A -> BO).

Ejemplo de Gramática lineal derecha:

P = {S -> a? | abT | abcT | abcd T -> S | cS | bcT | abe | abcd } que en sí es una Gramática libre de contexto. Téngase en cuenta que este tipo de

Gramática no forma parte de la Jerarquía de Chomsky, y que su empleo es más bien debido a que en este caso se puede identificar fácilmente la derivación que nos

lleva a alguna cadena determinada.

Ejemplo de Gramática Regular:

G= (N, T, P, oo )

N= {A, B,C, D. E} T

P = { A -> xA | yC | x,

C -> yA | xC | yE,

E^yB|yE|y }

{ x, y, z}

B -> xC

D-->xA

oo = { A }

xD | yE | x,

xB.

A => xA -^ xyC ==> xyyE -> xyyyE ==> xyyyy .

Nótese como las cadenas se construyen símbolo por símbolo y de izquierda a derecha en una forma muy sencilla. El no terminal siempre aparece como sufijo.

COMENTARIO FINAL SOBRE LAS GRAMÁTICAS: Existen algunas diferencias en los criterios para clasificarlas en alguno de los cuatro t'pos; por ejemplo, algunos

autores consideran que. Jas.-reglas lambda son válidas en las de tipo 2, otros reconocen a las Regulares por izquierda y por derecha; algunos opinan que en la

Gramática sensible al contexto basta que las reglas tengan menos símbolos a ta izquierda.que a la derecha. Ha sido considerada la definición más provechosa para

los objetivos del curso.

DERIVACIÓN A LA IZQUIERDA Y A LA DERECHA:

Sea G una Gramática libre de contexto y s una cadena de L(G); se le llama derivación a la i2quierda^i al derivar para obtener la cadena, se sustitulle siempre el

símbolo no terminal qué esté más a la izquierda. Similarmente, la derivación ala derecha ocurre cuando el símbolo que se deriva es el de más hacia la derecha.

Estos dos tipos de derivación no se pueden expresar por árboles de derivación, porque en éstos no sé conoce el orden en que se han aplicado las reglas.

ARBOLES DE DERIVACIÓN

Es una forma de indicar como una Gramática independiente de contexto deriva una palabra particular. Los nodos de las hojas del árbol son símbolos terminales y

los nodos interiores son los no terminales. Puede ocurrir que secuencias de derivación diferentes correspondan al mismo árbol de derivación.

Es útil en muchos casos presentar las derivaciones como árboles. Estos diagramas conocidos también como árboles de análisis gramatical suponen una estructura

$obre las palabras-de. un-lenguaje, y son de utilidad en aplicaciones tales como la compilación de los lenguajes de programación.

Si un vértice inferior se denomina A y sus hijos están etiquetados con Xi Xa ... , Xn entonces A - x^xa... Xn esuna regla de producción dé la Gramática.

¿Por qué no se pueden usar los árboles de derivación en Gramáticas que no sean libres de contexto?

EJEMPLO:

Dada G = ({a. b}, {0,1}. { a -> Oab a1 | bO.^. b --> Oa 1 }, {a}), determinar alguna

cadena s | s e L(G):

a => Oab =,0a1b => Oa10a = Oa110a = ObOHOa = ObOHObO = 010110b0

01011010 2/4 n\2 s=(oir(w) s =8

Su árbol de derivación equivalente es:

<a>

<0> <a>

<b>

<a> <1> <b> O

<b> o 1

8=01011010

El árbol se lee en forma similar a como se hace con los que se utilizan en las estructuras de datos: primero en profundidad.

Obsérvese como de la derivación simple al árbol no hay ambigüedad, pero sí cuando se da como dato el árbol y deseamos saber el orden en que ocurrieron

las derivaciones que la produjeron. Como en muchas ocasiones no importa ese orden, esto no representa problema alguno.

EJEMPLOS PROPUESTOS:

1) Determinar el árbol de derivación para s = 000 en la Gramática anterior.

2) Desarrollar una frase válida de un lenguaje natural (como el castellano) utilizando

las reglas de producción adecuadas.

3) Diseñar el árbol de derivación para la expresión ( a + b ) * c . ¿Cuáles serían su

árbol de análisis sintáctico y su árbol sintáctico?

4) Diseñar un árbol que genere la cadena discurrí ;= b * b - 4 * a * c.

5) Dada G = ( { S, A }, { a, b }, { S -> aAS a, A -> SbA ba }, { S }), SS

demostrar con un árbol de derivación que a2 b2 e L(G).

GRAMÁTICAS AMBIGUAS Y UNÍVOCAS

Una Gramática puede tener más de un árbol de derivación que genere una cadena

determinada. Para demostrar que una Gramática es ambigua lo único que se

requiere es encontrar una cadena que tenga más de un árbol de derivación que la

produzca. En contraposición, la unívoca es una Gramática libre de contexto que tiene

asociado un solo árbol de derivación para toda cadena de L(G).

Un Lenguaje L se llama UNÍVOCO si existe una Gramática unívoca que lo genere y

si no es así se lo llama AMBIGUO.

Como la cadena a - b + c se puede producir por cualquiera de los dos árboles, la

Gramática G es ambigua.

NOTA: Para el diseño de un compilador se utiliza una Gramática no ambigua o bien

una ambigua con reglas adicionales para resolver las ambigüedades.

EJEMPLOS PROPUESTOS:

a) Determinar si G es ambigua ó unvigua

P = { <cadena> ::^ <cadena> + <¡d> <cadena> - <id> <¡d>,

<id> ;:= a b c d} Considérese la cadena a b +c.

b) Determinar si G es ambigua o unívoca:

G=({E}, {(,).+,*. id}, {E^E+E EA E

(E)

¡d }. { E }),

En este caso, como la variedad de identíficadores válidos es muy grande, se

considera en la teoría de compiladores como si id fuera un terminal definido.

FORMA CORRECTA PARA GENERAR REGLAS DE

PRODUCCIÓN EN GRAMÁTICAS NO AMBIGUAS

Se toman como modelo las dos operaciones múltiples del punto anterior, y se aplica

de manera similar para cualquier otra operación válida de un Lenguaje de

programación, que tiene que corresponder a alguno de los dos casos.

Reglas para asignación múltiple (ASOCIATIVA POR LA DERECHA):

<íd> = <asigna>

a <id> = <asígna>

b <¡d>

P ^ { <asigna> ::= <¡d> ^ <as¡gna> | <id>, <¡d> ::=- a | b | c |...}

Reglas para sustracción múltiple (ASOCIATIVA POR LA IZQUIERDA)

<resta>

<resta> <íd> c

<id> b

GRAMÁTICAS CON LAMBDA O DECIDIBLES:

Son aquellas en las cuales Á e L(G). Debe existir una derivación que nos lleve a X

partiendo del símbolo inícíal-

Ejemplo

P ^ {A ^ Á, . .} Con Reglas k Si decidible.

P =- {A ^ B, B -^ Á, ...} Con Reglas ^ Sí decidible.

P = {A -> Bx, B > ?., ...} Con Reglas \ No decidible

TEOREMA:

Si U y La son Lenguajes regulares, entonces Li u Ls, Li • Ls, Li" , \-z , también son

Lenguajes regulares.

JERARQUÍA DE OPERADORES DE LENGUAJES: Si una expresión compuesta (

tal como Li * • L2 • L3 u i.^} contiene varias indicaciones de operaciones válidas con

Lenguajes, éstas se efectuarán en el siguiente orden:

a) Paréntesis b) Cerradura c) Concatenación d) Unión.

TEORÍA DE COMPILADORES

Las Gramáticas tipo O y 1 muestran un buen número de propiedades indecidibtes. En

las Gramáticas de tipo O, por ejemplo, no se puede determinar algorítmicamente sí

una frase dada es producto de ella o no; es decir, no se puede saber si una Máquina

de Turing diseñada para reconocer esas frases se detendrá o no durante el

transcurso de esa computación.

La teoría de la computabilidad ha permitido descubrir muchas propiedades de los

Lenguajes y sus reconocedores, y ha permitido también el diseño de los Lenguajes

de programación y de sus correspondientes Autómatas encargados de reconocerlos

y traducirlos a expresiones más simples: los compiladores.

La Gramática que describe a los Lenguajes de programación usuales es de tipo 2 y

el analizador sintáctico de un compilador es un Autómata de pila. Así mismo, el

analizador lexicográfico de un compilador es up Autómata finito, porque la Gramática

que se emplea en la definición léxica de un Lenguaje como Fortran o Pascal es de

tipo 3.

De hecho, el ejemplo de una Gramática tipo 3 mostraría como se pueden obtener los

nombres de los componentes Léxicos para uno de esos Lenguajes.

Et conocimiento sobre los conceptos teóricos de los Lenguajes formales se remonta

a 1936, fecha anterior al surgimiento de las computadoras electrónicas digitales.

Como dato interesante, se puede comentar que el primer compilador de Fortran

requirió para su implantación de 18 años de trabajo en grupo. Con las nuevas

técnicas, estudiadas en este curso, un compilador de calidad aceptable se puede

diseñar en un curso de un semestre.

Programa

Fuente

(ASCII) COMPILADORP-> programa Objeto

(máquina)

Mensajes de error

Programa Fuente

Analizador Léxico

Analizador Sintáctico

Analizador Semántico

TOKENS O COMPONENTES LÉXICOS:

Es cualquiera de los símbolos terminales que se manejan en la construcción de

líneas de programa en un Lenguaje de alto nivel. Se definen como un par ordenado

Token = (Tipo, Valor).

EJEMPLO:

Sea discrim := b * b - 4 * a * c ; if discrim > O then .

fragmento de programa-

(Identificador, "discrim") (operador, :=)

(operador, *) (operador, -)

(identifícador, "a") (identifícador, "c")

(palabra reservada, ií) (op. relación, >)

(palabra reservada, then)

determinar los tokens de este

(idenííficador, "b")

(constante, 4)

(separador, ;)

(constante, 0)

CASO DE ESTUDIO

Hacer un seguimiento de la línea de programa posición := inicial + velocidad * 60,

y explicar como se va procesando en cada una de las etapas de un compilador.

ANALIZADOR LÉXICO

Función: Comprobar la correcta construcción de los tokens. A ciertos componentes

léxicos (como los id) se les introduce en la tabla de símbolos-

Errores típicos:

Identifícadores mal estructurados: 4AC, ©quantum, yo.tu, posición, etc.

Constantes mal estructuradas: +-4.6789, 6,900, 90+25, etc.

Operadores mal estructurados: :=,=>, o (en C), etc.

Palabras reservadas mal estructuradas: PRfNTF, print, suitch, etc

ANALIZADOR SINTÁCTICO

Función: Comprobar el correcto acomodo de los tokens. En esta etapa se genera el

árbol sintáctico de la expresión.

Errores típicos:

Paréntesis mal anidados: (()((),())(()), 0(0) ) ((), etc.

a + b ^ c. ... d + * c, ... , etc.

ANALIZADOR SEMÁNTICO

Función: Revisa e! programa fuente para tratar de encontrar errores de este tipo y

reúne información sobre los tipos de los datos. Si es necesario, hace un ajuste de los

mismos.

Errores típicos:

Los indicados con el mensaje Type mismatch.

Cuando se usa una variable real como argumento de un for, o subíndice de

una matriz, etc.

S¡ se suman matrices con vectores, etc.

GENERADOR DE CÓDIGO INTERMEDIO

Función: Algunos compiladores producen una representación intermedia explícita

de programa fuente. Se puede considerar ésta como un programa para una máquina

abstracta. Se propone como lenguaje el "código de tres direcciones", en el que cada

instrucción tiene como máximo tres operandos.

temp1 := enteroareal(60)

temp2 :- id3 * temp1

temp3 := id2 + temp2

id1 .^ temp3

OPTIMIZADOR DE CÓDIGO

Función: Para mejorar e! código intermedio, de modo que resulte un código de

máquina más rápido de ejecutar. Existe mucha variación en !a magnitud de la

optimización que realizan tos distintos compiladores, e inclusive, algunas

optimizaciones son triviales. Es importante que el diseñador especifique qué

entiende por este término.

Considérese el siguiente ejemplo:

temp4 := id4 *temp3

temp6 := Íd4 *temp3

temp4 := id4 *íemp3

temp6 := t2mp4

témpt ;=id3 '60.0

id1 ;= ld2 + temp1

GENERADOR DE CÓDIGO

Función:' Produce el código objeto, que por lo general consiste en código

relocalizable o código ensamblador. Las posiciones de memoria se seleccionan para

cada una de las variables usadas por el programa; después, cada una de las

instrucciones intermedias se traduce a una secuencia de instrucciones de máquina

que ejecuta la misma tarea. Un aspecto decisivo es la asignación de variables a

registros.

Destino Origen

MOVF Bx, id3

MULF Bx. #60.0

MOVF Ax, ld2

ADDF Ax, Bx

MOVF id1, Ax

Para mayor información sobre este tema, consultar el texto de Aho

mencionado en la bibliografía.

FORMA NORMAL DE CHOMSKY (CNF)

Se presenta cuando ef lado derecho en todas las reglas de producción de una

Gramática libre de contexto consiste en un símbolo terminal o exactamente dos no

terminales.

Considérese el siguiente ejemplo:

temp4 := id4 *temp3

temp6 ^ ¡d4 *temp3

temp4 ;=id4 *temp3

temp6 := temp4

temp1 ;=¡d3 *60.0

¡d1 := ¡d2 + temp1

GENERADOR DE CÓDIGO

Función: Produce el código objeto, que por lo general consiste en código

relocalizable o código ensamblador. Las posiciones de memoria se seleccionan para

cada una de las variables usadas por el programa; después, cada una de las

instrucciones intermedias se traduce a una secuencia de instrucciones de máquina

que ejecuta la misma tarea. Un aspecto decisivo es la asignación de variables a

registros. ;

Destino Origen

MOVF Bx, id3

MULF Bx, #60.0

MOVF Ax, ¡d2

ADDF Ax, Bx

MOVF ¡d1, Ax

Para mayor información sobre este tema, consultar el texto de Aho

mencionado en la bibliografía.

FORMA NORMAL DE CHOMSKY (CNF)

Se presenta cuando el lado derecho en todas las reglas de producción de una

Gramática libre de contexto consiste en un símbolo termina! o exactamente dos no

terminales.

Obsérvese que. para una Gramática en Forma Normal de Chomsky, el árbol de

derivación para cualquier derivación está bastante bien construido ya que, excepto

en las hojas, el árbol es binario.

EJEMPLO:

P1 ={S->xSy, S->xy}

P2 = { S -> XM. S -> XY, M ^ SY. X -^ x, Y ^ y}

L(G^)=={xtY neN}^L(G2) -•-Gi - G2

Observar que Gs está en Forma Normal de Chomsky.

TEOREMA

Si G es una Gramática libre de contexto, entonces existe otra Gramática libre de

contexto G' expresada en CNF tal que G ~ G\

Comentario: También es posible hacer la conversión cuando la Gramática tiene en

todas sus reglas al lado izquierdo un solo no terminal, y que la Gramática no sea

decidible.

PROCEDIMIENTO PARA TRANSFORMAR UNA GRAMÁTICA

A LA CNF:

PASO 1 ) Se transforman las combinaciones de terminales y no terminales, o bien

donde haya más de un terminal al lado derecho de las composiciones. Para cada

Terminal a e P, se define un no terminal específico A, y la regla A —^ a con lo que se

sustituye cada ocurrencia de a por A.

EJEMPLOS:

S->abMa

S ^ ABMA

A -^ a

B->b

- S^-xy

•XY

X-^x

Y-^y

PASO 2 ) Se transforman las reglas en las que en el lado derecho hay más de dos

no termínales. Se hace de la siguiente manera: La regla N -> N1 N3 N3 ... N( se

sustituye por el encadenamiento de t-1 reglas:

N->N,Ri R.,-^N2R2 R^NaRs .. Rt-2-^Nt-iNi

PASO 3 ) Se transforman las reglas que contengan a la derecha un solo símbolo no

terminal. Se hace de la siguiente manera:

Dadas las reglas:

Mr ->Nt-i NM >N,-2 ... N2 -?-Ni

Si N1 -> A, entonces N( ->- A

Si N1 -> AB, entonces Ni --> AB

y se eliminan las composiciones innecesarias.

EJEMPLO:

A-^B, B-~>R, R->0 es sustituida por: A->0

Los pasos anteriores se resumen en la siguiente tabla:

paso A-> B Exs:

1 B e (NUT)*-N* X-^aSb2

2 B >2 X >ST2

3 B e N X^U

EJEMPLOS PROPUESTOS:

1) Reducir a CNF la siguiente Gramática:

N={S.M, N} T={a, b, c } gO-(S}

P={ S -> cMNc ac, M -> aMa | c | MN, N -^ bNb | c }

2) Reducir a CNF la siguiente Gramática:

N=4 A, B, C, D, F}

A-^xy B >DEF - C->y

A->Bx C-^DC D->xx

E->FA

E-^yCy

A-->xEx

B->zC

C^xyF

C-^FA

D^yB

D-^xE

F->AC

F-^B

SISTEMA DE PROCESAMIENTO DIGITAL DE VOZ PARA EL

RECONOCIMIENTO DEL HABLA

NIVEL ACÚSTICO NIVEL FONÉTICO

NIVEL LÉXICOG NIVEL SINTÁCTICO NIVEL S&-MÁNTICO NIVEL PROSÓDICO

APLICACIÓN

MODULO II

MÁQUINAS DE ESTADO FINITO

Es un Modelo abstracto de una máquina con memoria interna primitiva. Se

puede considerar a un computador como una máquina de este tipo. Una Máquina

de Estado Finito M consiste en:

a) Un conjunto finito I de símbolos de entrada.

b) Un conjunto finito O de símbolos de salida.

c) Un conjunto finito S de estados.

d) Una función estado siguiente f de S XI en S .

e) Una función salida g de S XI en O .

f) Un estado inicial Go > incluido en S.

Se expresa de manera sintetizada como: M = (I ,0 ,S , f, g, ^o).

En una Máquina de Estado Finito cuando ingresa un símbolo de entrada ocurre

una Transición , que consiste en que primero se produzca un símbolo en la salida y

posteriormente (pero de manera inmediata) exista un cambio de estado-

Símbolo de salida = f (estado actual, símbolo de entrada) = g.

Estado siguiente = f (estado actual, símbolo de entrada) == f.

Sin embargo, si el estado actual fuese D, por ejemplo, la salida podría ser 1,

aún con la misma entrada A.

Se emplea este modelo para representar todos aquellos sistemas en los

que la salida no es función exclusiva de la entrada, sino también de un estado

o situación actual implícita en el mismo.

Ejemplos sencillos de Máquinas de Estado Finito:

a Máquina para venía de refrescos.

a Sistema tetefóntco.

a Circuitos secuencíales digitales.

" Juegos de combate,

EJEMPLO:

Representar ia Máquina de Estado Finito siguiente por medio de un diagrama

de transición y por una tabla de transición.

i -{a,b} .-

f= {f(qo,a-)=;q:i,

f(q1,a)=^,

f(q2,a)^qü,

g^gíqo.a^x,

g(qi,a)=x,

g ( q2. a ) ^ z,

0?{x,y.z}

S^{qo, qi, q2Í c,o={qo}

'f(qo,-b'),=.q^,-,

•f(q,,b).=qi^i:--

f(q2.b)=.q;i^

gCqo.b^^y^

g ( q-,,.b,) ^ z,-

g ( q2, b ) = yí

DIAGRAMA DE TRANSICIÓN DE M: Es un digrafo G, en donde los vértices son

los estados; el estado inicial se señala con una flecha gruesa sin origen. Si se parte

del estado q,r, y una entrada i proporciona una salida o, y se cambia al estado q?,

se traza un arco dirigido de qm a qn y se marca como i / o.

Cadena de salida: Sout=x z z z x z x x y

Estados recorridos: qo q1 q2 q1 q1 q2 q0 q1 q2 q1

deia^> Una ventaja significativa di Máquina de Estado Finito s si diagrama de transición es que el comportamiento e puede analizar en una forma sumamente sencilla.

S/i a b

qo qi,x q2,y

qi q^,x q1z

q2 qo,z qi ,y

s/ f 9

i a b a b

qo qi q2 x y

qi q2 qi x z

q2 qo qi z y

Las dos variaciones anteriores representan la tabla de transición, el alumno

deberá elegir la que le resulte más adecuada. Esta representación es muy

importante en la ¡mplementación en una computadora de la Máquina.

Dada una cualquiera de las tres representaciones posibles de M debe ser

posible, sin ambigüedades, de obtenerse ¡as otras dos.

EJEMPLO:

Diseñar un diagrama de transición y IOSJS conjuntos que definen a M.

EJEMPLO:

Diseñar una Máquina de Estado Finito que represente un sumador binario en

serie.

10010010+

10100111=

100111001

Ejemplo de una

suma binaria en serie

De acuerdo al conocimiento, tanto, de la operación de la suma como de las

Máquinas de Estado Finito, se determinan tos conjuntos:

1 = {00, 01, 10, 11 } 0= {O, 1 } S= {SA,CA} GO - { SA }

Comprobación de la suma anterior::

S,,, ^ 0-1 11 01 00 10 01 00 11

Soui ^1,0.0 1 1 1 0 0

SA •,5A CA- CA 'SA . SA SA SA CA

La versión .previa ,de sumador tiene el inconveniente de que el bit más

significativo se pierde si el resultado excede en un bit a la longitud de los sumandos.

Proponer una variante al sumador anterior tal que el resultado lo entregue Íntegro.

Sin embargo, no existe una Máquina de Estado Finito que pueda realizar la

multiplicación binaria en serie- ¿Por qué?

EJEMPLOS PROPUESTOS:

Diseñar una M en cada inciso, considerando las especificaciones y

considerando como dato de entrada posible cualquier cadena de bits válida. Tales

podrían ser cadenas cómo 0010001110, 1101, 11111, 010101010, etc.

a) S¡ el dato de entrada contiene una cantidad par de 1 la salida es 1, O en casocontrario.

b) Si la entrada es una cadena con una cantidad de 1 ¡gual a un múltiplo de 3 la

salida es 1; O en caso contrario.

c) Si la entrada contiene dos o más bits en 1 la salida es 1; O en caso contrario.

d) La salida es 1 si la cadena de entrada es exactamente 101; O en caso contrarío.

e) La salida es 1 si la cadena inicia con 101; O en caso contrario.

f) La salida es 1 si la cadena contiene exactamente un 0; O en caso contrarío.

CONCEPTOS ADICIONALES:

Existen muchos diferentes tipos de Máquinas de Estado Finito para modelar

máquinas de cómputo, que son llamadas Máquinas secuenciales. En el tipo

tradicional las salidas corresponden a transiciones entre estados. Las

representaciones de este tipo son conocidas como Máquinas de Mealy, ya que

fueron primeramente estudiadas por G. H. Mealy en 1955. Existe otro tipo importante

de Máquina de Estado Finito con salida, donde esta última es determinada solo por

el estado. Se le conoce como Máquina de Moore, ya que E. F. Moore introdujo este

tipo de Máquina en 1956. Se observa una estrecha relación de las Máquinas de

Mealy con las de Estado Finito y de la de Moore con los Autómatas de Estado Finito.

Una Máquina de Moore puede convertirse en una de Mealy equivalente

añadiendo más estados y haciendo las modificaciones necesarias.

Queda para el estudiante investigar más sobre estas dos variantes de M.

MODULO III

AUTÓMATAS DE ESTADO FINITO

Es toda Máquina de Estado Finito en la que el conjunto de símbolos de

salida es {O, 1 } y donde el estado^actLíai^Qtefrwfía-eróltimtrdate-de-saiKia--

Aquellos estados para los cualeÍTiÍI último dato de salida es 1 se denominan

estados de aceptación. En todo Autómata A debe haber cuando menos un

estado de aceptación y se recomienda que no todos lo sean.

La razón por la que el conjunto O debe ser { O , 1 } resulta razonable

debido a que se les utiliza en la computación y en la electrónica digital, donde se

opera con et sistema binario. Se observa que en un compilador la salida es,

precisamente, et algoritmo en lenguaje máquina, obtenido a partir de la entrada

en caracteres ASCII.

La segunda característica surge de la necesidad práctica de saber en qué

estado se termina el recorrido en el diagrama de transición para una cadena de

entrada, sin importar los estados intermedios que se van obteniendo. Si se

conoce el estado final, entonces también se deberá conocer cuál fue el último bit

de la cadena de salida.

El Autómata de Estado Finito se emplea en vez de la Máquina, cuando no

es tan importante considerar las salidas obtenidas al ir recibiendo los símbolos

de la cadena de entrada, sino solamente conocer el último bit de salida.

EJEMPL:

Trazar el diagrama de transmisión de la Máquina de Estado Finito definida

en la tabla;: demostrar que es también ;un Autómata y determinar el conjunto de

estados de aceptación:

s i w x y z

q0 q1,0 q2,1 q0,1 q1,0

q1 q1,0 q0,1 q1,0 q0,1

q2 q2,1 q1,0 q1,0 q0,1

Estados de aceptación: qo, q2 Estado de no aceptación: q1

Es un Autómata de Estado Finito en razón de que en todos los arcos que

llegan a los estados de aceptación se tiene la indicación de bit de salida en 1, y O

en los de no aceptación. Conociendo en cuál estado se termina el recorrido en el

Autómata, se puede conocer cuál fue el último bit de salida aún sin conocer la

cadena de entrada.

Sin= y x x z w y x w // cadena de entrada.

qo qo q2 qi qo qi qi qo qi // estados recorridos.

SÍ un Autómata de Estado Finito recibe como dato de entrada una cadena o arreglo, se puede concluir el recorrido en el Autómata o en un estado de

aceptación o en uno de no aceptación; la clase de estado en la cuál se termina establece cuando una cadena es aceptada por el Autómata. Como el recorrido

finalizó en este caso en un estado de no aceptación, la cadena vxxzwvxw se considera que no es aceptada por el Autómata, ésto significa que no cumple

con las especificaciones que se dieron para su diseño.

La tabla de transición para el Autómata, ya simplificada, quedaría:

S/I w x y z

q qi q2 qo q1

qi qi Qo qi qo

q2 q2 q1 q1 qo

DEFINICIÓN FORMAL DE AUTÓMATA DE ESTADO FINITO

UN AUTÓMATA DE ESTADO FINITO CONSISTE EN:

a) Un conjunto finito I de símbolos de entrada.

b) Un conjunto finito S de esíados-

c) Una función estado siguiente f de S x I en S.

d) Un subconjunto A S de estados de aceptación.

e) Un estado inicial go E S.

Se expresa en notación de conjuntos como: A = (1 , S , f, A , ao).

Nótese que en las tres representaciones de un Autómata, el especificar los

estados de aceptación hace innecesario definir la función g, por obviedad.

Para el Autómata expresado en el ejemplo anterior, se tiene:

I =={w,x, y. 2} S=={qo.qi,q2} A = { qo,q1,q2 } go={qo}

f= {f(qo,W) = q1,,.. , f(q2,z)=qo} <———son 12 en total.

AUTÓMATAS EQUIVALENTES

Si dos Autómatas aceptan exactamente las mismas palabras, se dice que tales son equivalentes. El conjunto I debe ser el mismo para ambos, mientras

que ao y S pueden variar y la función f necesariamente cambia entre ellos.

EJEMPLOS PROPUESTOS:

1) Diseñar un Autómata Finito que acepte únicamente los arreglos con I = {a, b }

pero que no contengan a. Sm = un n e Ko

2) Diseñar un Autómata Finito que acepte cadenas no nulas formadas con los

símbolos del conjunto I = { a. b, c } y que no contengan ni a ni c.

S,n = un n e K

3) Diseñar un Autómata Finito con 1 :=: { a, JÜ } que acepte cadenas con una

cantidad impar de letras a.

4) Diseñar un Autómata Finito con 1 = { a, b } que acepte palabras en las que

siempre que aparezca una b esté seguida necesariamente por una a (sin dos

letras b consecutivas).

5) Diseñar un Autómata Finito con t = { a, £»} que acepte arreglos que inicien

con baa.

6) Dado el diagrama de transición determinar:

a) ¿Se puede transformar esta Máquina en un Autómata Finito?

b) ¿Qué sistema real representa?

EJEMPLO:

Diseñar e implementar un Autómata que acepte los nombres de identificadores válidos de un lenguaje de programación típico como C o Pasca!.

Este diseño es un pequeño subconjunto de un analizador léxico.

Se definen las clases de los símbolos de entrada que se consideran en los arcos como tipos de datos para simplificar la representación del diagrama:

dígito: 0. 1,2,...,9

letra: A, B, C, ... , Z, a, b, c, ..,z._.

Se tomará como base el criterio de que un identifícador inicia con una letra y después puede llevar dígitos y/o letras, pero nunca caracteres diferentes a

estos dos tipos.

Al dibujar el diagrama de transición se debe tomar en cuenta que por conveniencia los arcos que corresponderían a situaciones de no aceptación se

omiten, quedando como entendido que irían todos a un estado de rechazo. En realidad el estado qi se puede omitir debido a que llegando a él, de todos modos

la cadena no va a ser aceptada, pero se incluye para que con tres estados el ejemplo sea más demostrativo.

La primera versión de la implementación puede ser la siguiente:

Estado <- O

LEER siguiente símbolo de entrada

MIENTRAS no (fin de cadena ) HACER

OPCIÓN (Estado) DE

0: SI ( Símbolo actual = letra )

ENTONCES ( Estado ^ 2 )

SINO SI ( Símbolo actual = dígito)

ENTONCES ( Estado <- 1 )

SINO (Error_rutina)

1: Error_rutina

2: SI (Símbolo actual = letra)

ENTONCES ( Estado <- 2 )

SINO SI ( Símbolo actual = dígito )

ENTONCES (Estado <-2)

SINO ( Error J-utina )

, FINOPCIÓN

LEER Siguiente símbolo de entrada

FINMIENTRAS

SI ( Estado =2 ) ENTONCES (Error_rutina)

Sin embargo, la opción anterior no debe utilizarse para implementar un Autómata, pues en un diseño en el que existan varios estados con muchas entradas posibles, como se podrá observar, resultaría en una instrucción alternativa múltiple con un rango gigantesco.

Una segunda versión, mucho más práctica, utiliza una tabla de transiciones en la cual se consulta cuál será el valor del siguiente estado. La gran ventaja de esta variante es que para cambios en el diseño original del Autómata, las modificaciones se hacen en la tabla solamente.

APLICACIÓN DE AUTÓMATAS Y MÁQUINAS DE ESTADO

FINITO

MÁQUINA PARA VENTA DE REFRESCOS:

Diseñar una máquina que reciba monedas de 5. 10 y 25 centavos y que cuando complete 30 i entregue al usuario, una lata con refresco.

Primera versión (como Autómata):

I ={5, 10, 25}

S ={0, 5. 10, 15. 20, 25. 30+}

oo = { O }

A = { 30+ }

Limitaciones del modelo propuesto anteriormente:

a No regresa el cambio, pues la salida es exclusivamente, entrega o no

entrega una lata de refresco, dependiendo si se llega al estado de

aceptación.

a La salida consiste en un solo tipo de refresco por esa misma razón.

a Para regresar al estado inicial se debe contar con una entrada que

reiniciaiize e! sistema.

Segunda versión (como Máquina):

I ={5, 10.25.Bn.Bd}

O = {n, 5, 10, 15, 20, 25, Normal, Dieta }

S ={0.5, 10, 15.20.25,30}

<yo = { O }

CIRCUITOS DIGITALES SECUENCIALES

RECONOCEDOR DE IMPARIDAD DE PULSOS.

Encontrar un Autómata Finito cuyo comportamiento corresponda al del circuito anexo, en que los estados finales correspondan a una salida 1.

Supóngase que existe el tiempo suficiente entre cada cambio de los valores de la entrada para que las señales se propaguen y para que la red

alcance una configuración estable.

EJEMPLO: Representar por medio de un Autómata el siguiente circuito digital secuencia!. No tomar en cuenta la posible inestabilidad en el circuito.

S / I 0 0 0 1 1 0 1 1

a b a b a b a b a b

0 0 1 1 1 1 1 1 1 1

0 1 1 1 1 1 0 1 0 1

1 0 1 1 1 0 1 1 1 0

1 1 1 1 1 0 0 1 0 0

s/I 0 0 0 1 1 0 1 1

q0 q3 q3 q3 q3

q1 q3 q3 q1 q1

q2 q3 q2 qs q2

q3 q3 q2 q1 qo

Una ventaja de modelar matemáticamente los circuitos digitales

secuenciales es que el análisis es más sencillo en el diagrama de

transición que en el diagrama electrónico. Además ésto ha permitido la

creación de aplicaciones como Workbench o Spice.

Diseñar et diagrama de transición correspondiente.

La anterior es la tabla de transición de una Máquina de Estado Finito.

La salida y el siguiente estado no se consideran cuando la entrada (en el

reloj) es O, porque éstos no ocasionan acción alguna en el circuito.

El circuito contador de tres bits se obtiene a partir de tas ecuaciones

para Di, Da y Ds, recientemente obtenidas.

Nótese que las tablas de transición se empleaban en estas

aplicaciones, aunque sin haberlas justificado, en cursos de electrónica

digital. Para obtener mayor información detestas aplicaciones consúltense

libros de esta materia.

Tabla de verdad para el Flip Flop Tipo D:

D CK Qn Qn+l

0 0 0 0

0 0 1 1

0 1 0 0

0 1 1 0

1 0 0 0

1 0 1 1

1 1 0 1

1 1 1 1

APLICACIONES EN INTELIGENCIA ARTIFICIAL

EJEMPLO:

a) En la orilla norte de un río se encuentra un hombre junto con un lobo,

una gallina y una cubeta con maíz- Hay un bote con capacidad suficiente

para transportar al hombre y otra cosa. Todos los elementos deben cruzar

al río sin que queden solos lobo-gallina o gallina-maíz. ¿Cómo se resuelve

el problema?

Hombre (H), Lobo (L), Gallina (G), Maíz (M)

¡ =• { H, HL, HG, HM } Indica quién está cruzando el río.

b) Redes Neuronales: .Históricamente, los Autómatas Finitos se utilizaron

por primera vez para modelar redes de neuronas. Diseñar un AFD cuyo

comportamiento sea equivalente a la red neurona! de la figura. Los

estados finales del Autómata corresponden a una salida 1 de la red. Cada

neurona tienen sinapsis excitantes ( O ) e inhibitorias ( • ). Una neurona

produce unasalida 1 si el número de sinapsis excitantes con entrada 1

excede al de las inhibitorias con entrada 1, por al menos el umbral de la

neurona (el número que se encuentra dentro del triángulo). Supóngase

que existe tiempo suficiente entre cada cambio de valor de entrada para

que las señales se propaguen y para que la red alcance una configuración

estable.

S / I 0 1

Y1y2y3 y1y2y3 y1y2y3

0 0 0 0 0 0 0 0 1

0 0 1 0 1 1 0 0 1

0 1 0 0 1 0 1 0 1

0 1 1 0 1 1 1 1 1

1 0 0 0 0 0 1 0 0

1 0 1 0 1 0 1 0 1

1 1 0 1 1 0 1 0 0

1 1 1 1 1 0 1 1 1

s/I 0 1

qo qo q1

q1 q3 q1

q2 q2 q5

q3 q3 q7

q4 qo q4

q5 q2 q5

q6 q6 q4

q7 Q6 q7

AUTÓMATA FINITO DETERMINISTA (AFD)

Es un dispositivo que puede estar en uno cualquiera de un número finito de

estados, uno de los cuales es el estado inicial y por lo menos uno es un estado

de aceptación. A este dispositivo está asociado un flujo de entrada que consiste

en una secuencia de símbolos de, un alfabeto determinado.

La máquina tiene la capacidad de detectar los símbolos conforme llegan y,

basándose en el estado actual y el símbolo recibido, ejecutar una transición, que

puede ser un cambio a otro estado o la permanencia en el actual.

La representación de un AFD no debe contener ambigüedades, de lo cual

le viene el nombre de determinista, el nombre de finito es debido a que aunque

analice una cantidad infinita de posibles cadenas de entrada, la cantidad de

estados es limitada.

AUTÓMATA FINITO NO DETERMINISTA (AFND)

Cuando se encuentra en un estado de donde parten arcos múltiples con el

mismo símbolo x, si x es un dato de entrada, la situación es no determinista, ya

que no es seguro el siguiente estado-

Un ejemplo de un AFND sería:

Dada una cadena de entrada Sm, se considera que tal arreglo es aceptado

si existe por lo menos un recorrido en el Autómata que nos lleve a un estado de

aceptación, sin importar que existan otros para la misma cadena que terminen

en uno de.no aceptación.

Por ejemplo: Si la cadena de entrada es Sin = abbaab, obsérvese que

cuando llega el segundo símbolo de entrada (b) es en una situación en la que se

está en un estado (qi) en el cual no está definido lo que sucede para esa b; en

ese caso la cadena de entrada se rechaza.

Sea sin = a a b la cadena de entrada

Qo q1 q0 q0 x la cadena es aceptada

Q2 q0 x poruqe exiate un recorrido

Q2 / que permite en el estado q2

RELACIÓN ENTRE AUTÓMATAS Y GRAMÁTICAS

Una Gramática Regular y un Autómata de Estado Finito son. en esencia, lo

mismo ya que cualquiera de ellos es una especificación de un Lenguaje Regular.

Dado el Autómata que reconoce números reales y exponenciales sin signo

(véase una clase anterior), se puede construir una Gramática Regular que

produce tal lenguaje

a) Los símbolos terminales de G son los de entrada de A.

b)J-os estados se convierten en los símbolos no terminales.

c) £1 estado inicial se transforma en el símbolo inicial.

d) Las composiciones corresponden a los arcos dirigidos. Si existe un arco

con la marca x de A a B se escribe la regla de producción A -> xB. Además, si

hay un lado con la marca x de un estado A a un estado de aceptación, se incluye

la composición A --> x.

Por ejemplo:

aN={A.B,C,D}

T={a.b}

cro={A}

P = {A -> aB bC

C->aC bD,

D -> aB bB

A -y- a, A -> b

bD, B-^aB,

bD,

B->a.

C->a. D -^ a. D -> b}

Si solamente existieran los Autómatas Finitos Determinísticos,

¿Cómo se podría diseñar el Autómata asociado con esa Gramática en

particular, por ejemplo? Por otro lado, es recomendable en casos en que

una Gramática es difícil de diseñar, mejor crear el Autómata asociado, y

obtener del diagrama de transición las reglas gramaticales.

Problema inverso: Partiendo de una Gramática Regular, determinar el

Autómata Finito que acepta las cadenas de L(G).

Ejemplo: Sea G = (N, T, P, oo)

N-{S,A.B} T={a,b} oo = {S}.

P = { S -> aS | bS | aB . A -> bB , B ~> aB | aA | b}

Diseñar el AFND que acepta los arreglos de L (G), aplicando el

procedimiento anterior, en sentido inverso y obtener conclusiones.

Sea G = (N, T, P, oo) una Gramática Regular. Sean

Í=T

S=Nu{F},dondeF ¿ (NuT)

f ( A, x ) == { B | A --> xB é P } u { F | A "> x e P }

A={F}

CTO^Íüo} , .

Entonces el AFND llamado A acepta precisamente los arreglos de L (G).

CONVERSIÓN DE UN AFND EN UN AFD

TEOREMA: Dado un AFND llamado A, puede construirse un AFD

denominado A' que sea equivalente a A.

PROCEDIMIENTO: Sea A = (I, S. f. A, ero) un AFND. Sean

I' = 1

S' - P ( S )

A'^{XcS'|XnA^0}

üo' = { Oo }

f(X,x)=/0 si X=0

\ u f(5','^) VSeX si X^0

Entonces el AFD A' = (1' / S' , f , A', oo') es equivalente a A.

Nota: A' consiste en los subconjuntos de S* que contienen al menos un

estado de aceptación del AFND original.

Por ejemplo: Diseñar un AFD que reconozca las cadenas del Lenguaje

generado por la siguiente Gramática:

G - ({ S, C }. { a, b }. { S -> bS | aC , C -> bC | b }. { S }).

La caracterización del Lenguaje es L(G) = { bm a bn | m e Ko, n e K }.

TEOREMA: Un Lenguaje L es regular sí y sólo sí existe un AFD que

acepta únicamente las cadenas de L.

Ejemplo: Sea L el conjunto de arreglos aceptados por el siguiente AFD.

Construyase un AFD que acepte los arreglos L^ = {Xn... Xz Xi | Xi x^ ... Xn e L }.

Caracterizar L y LR.

Se empieza en el estado de aceptación y se traza el recorrido en sentido

opuesto hasta llegar al estado inicial. En seguida se convierte el AFND en un

AFD.

Ejemplo: Hacer lo mismo que en el problema anterior con el siguiente

Autómata.

Nótese que en este caso existen dos estados de aceptación, que serían

ambos estados iniciales según el criterio del anterior ejemplo. Se debe construir

primeramente un AFND que contenga un solo estado de aceptación. Enseguida

se procede como en el caso anterior.

Ejemplo: Transformar el siguiente Autómata en otro equivalente pero con

un solo estado de aceptación.

TEOREMA: Si L es un Lenguaje Regular, el Lenguaje LR = { Xn... X2 Xi | Xi

Xa... Xn e L} también es Regular.

Ejemplos para practicar:

a) Diseñar un AFD que acepte las cadenas del Lenguaje L = { bmababn |

m, n e No}

b) Diseñar sendos AFD que acepten: uno el 0 y el otro { Á.}

c) Diseñar un AFD que reconozca una cadena de paréntesis anidados y

equilibrados, asegurando que la profundidad del anidamiento no exceda un

determinado nivel y que los paréntesis se encuentren juntos los izquierdos y

luego los derechos. L = {(" )" | n = 1, 2, 3, ...}

TEOREMA: Si un Lenguaje Regular contiene cadenas de la forma x^n para

enteros n arbitrariamente grandes, entonces debe contener también cadenas de

la forma x^n, donde m ^ n.

Una consecuencia inmediata de lo anterior es que L ^ { x^n | n e N } no

es Regular. Una consecuencia un poco más sutil es que los AFD carecen del

poder suficiente para analizar expresiones aritméticas que contienen paréntesis.

Si un AFD aceptara tales expresiones/entonces también tendría que aceptar las

de la forma (n )^ para enteros n arbitrariamente grandes. Sin embargo, el

teorema anterior implica que un Autómata de este tipo también debe aceptar

expresiones en donde el número de paréntesis izquierdos no sea igual al de

paréntesis derechos. Así, tal máquina aceptaría expresiones tanto incorrectas

como correctas.

REPRESENTACIÓN DE UN AFD.

Componentes de un Autómata:

n Unidad de entrada: cinta de entrada con palabra de entrada, cabeza de

lectura.

a Unidad de memoria (opcional): cintas de memoria para resultados

auxiliares, cabezas de lectura y escritura.

a Unidad de control: Controla el Autómata según un programa.

n Unidad de salida (opcional): cinta de salida para la palabra de salida,

cabeza de escritura-

OPERACIONES CON EXPRESIONES REGULARES

1. Unión de Lenguajes: L1 ^ L2. La unión de dos Lenguajes Regulares

es otro Lenguaje Regular.

Ejemplo: Sean U = { xm/ | m ¿ No } y L2 = { y^ | n ¿ No }. Evaluar L1 ^

L2.

L1 ^ L2^{x^y^ y^xim. n ¿ \o}

Entrando a la parte correspondiente del diagrama original, ya no se puede

pasar a la otra. El nuevo estado inicial sería de aceptación sólo si uno de los

iniciales originales lo fuera.

Dibular un arco con la misma etiqueta que tienen los que salen de los

anteriores estados iniciales, ahora partiendo del nuevo estado inicial (esto por si

m, n fueran 0).

2. Concatenacion de Lenguajes: L1 . L2. La concatenación de dos

Lenguajes Regulares es otro Lenguaje Regular.

Ejemplo: Sean L1 = { x^yxn | m, n e No} y L2 = { y"xy0 | ñ. o e No} .

Evaluar L1.L2.

L1 • L2 = { xmyxnyñxyo I m, n, ñ, o e No}.

I' A partir de cada estado de aceptación del primer diagrama, dibujar un arco

P hacia cada estado del segundo que sea el destino de un arco del estado inicial

de éste último. Rotular cada uno de estos arcos con la etiqueta del arco

correspondiente en el segundo esquema. Dejar que los estados de aceptación

del primero sigan siéndolo sólo si el estado inicial del segundo es también un

estado de aceptación.

3. Estrella de Kleene o Cerradura de un Lenguaje: ( L1 )*. La cerradura

de cualquier lenguaje Regular es también un Lenguaje Regular.

Ejemplo: Sea L = {x^ | m e No}. Evaluar L*.

L*={(xmy)*|m e No}.

El nuevo diagrama de transición implica la concatenación del esquema

original hacia atrás consigo mismo, además de que debe aceptar 'k.

Dibujar un nuevo estado inicial y conectarlo al diagrama original, de forma

similar a cuando se hace con la unión de conjuntos: por cada estado se dibuja

un arco con la misma etiqueta del nuevo estado inicial hacia el destino de un

arco del estado inicial del diagrama original y luego se designa a éste como

estado de aceptación.

Para que puedan aceptarse las repeticiones de las subcadenas se añade

un arco de cada estado de aceptación a tada estado que es el destino de un

arco del estado inicial. Cada uno de estos nuevos arcos se rotula con la etiqueta

que corresponda al arco del estado inicial.

Dado un alfabeto particular y usando las tres operaciones anteriores, se

pueden construir varios lenguajes a partir de bloques de construcción.

DEFINICIÓN; Una expresión regular ( para un alfabeto £ ) se define como

sigue:

a) 0 es una expresión regular.

b) Cada elemento de £ es una expresión regular.

c) SÍ p, q son expresiones regulares, entonces p u q también lo es.

d) Si p, q son expresiones regulares, entonces p • q también to es.

e) Si p es expresión regular, entonces p* también lo es.

TEOREMA: Dado un alfabeto £, los Lenguajes Regulares de £ son

exactamente los Lenguajes representados por las expresiones regulares de £.

Si p, q, r son expresiones regulares, entonces: ( p • q )*, ( q u p ) • r, q* u

(r • q ), etc. también son expresiones regulares-

Ejercicios para el alumno. Diseñar los diagramas de transición para las

operaciones indicadas en los siguientes incisos:

Ejemplo: ¿Cuáles de los lenguajes descritos por las siguientes expresiones

regulares para el alfabeto {x, y, z} son infinitos?

Ejemplo: Representar gráficamente la unión de a • ( b • a ) * con x • ( y • x

Ejemplo: Dibujar un diagrama de transiciones que acepte la concatenación

del lenguaje aceptado porA1 con el aceptado porA2.

Los arcos que salen del estado inicial de A2 se reproducen en todos los

estados de aceptación. Se eliminan los de A1 excepto cuando se acepta X en

A2.

Ejemplo: Construir una expresión regular que describa el lenguaje

aceptado por el siguiente Autómata:

MODULO IV

AUTÓMATAS DE PILA

Los símbolos que pueden almacenarse en la pila (símbolos de pila del Autómata) constituyen un conjunto finito que puede incluir alguno o todos los símbolos del alfabeto de ta máquina y quizás algunos símbolos adicionales que la máquina utiliza como marcas internas, tales como la indicación de la Pila vacía (#).

Las transiciones que ejecutan los Autómatas de Pila deben ser variantes de la siguiente secuencia básica: leer un símbolo de entrada, extraer un símbolo de la Pila, insertar un símbolo en la Pila y pasar a un nuevo estado ( o continuar en el mismo). Nótese que al trabajar con más información que el Autómata Finito, también se hacen más complejas sus transiciones.

El estado actual, el símbolo de entrada y el símbolo ubicado en la cima de la Pila determinan conjuntamente el nuevo estado y el símbolo que se insertará

en la Pila.

DEFINICIÓN FORMAL DEL AUTÓMATA DE PILA:

Un Autómata de Pita es un séxtuplo ordenado de la forma: S = (I, S, r,

/ A, cTu) donde:

I es el conjunto de símbolos de entrada o alfabeto de la máquina.

S es una colección finita de estados.

r es la colección finita de símbolos de la Pila.

r es una colección finita de Transiciones.

A es un subconjunto de S, y es la colección de estados de aceptación.

do es un elemento de S, y es el estado inicial-

¿Cómo se modificaría el diagrama anterior para que en las cadenas de entrada, la cantidad de x, y de y sea la misma, pero sin importar el orden en que aparezcan los símbolos?

Los Autómatas de Pita se pueden utilizar para analizar cadenas en forma similar a como se usan los Autómatas Finitos. Una cadena que ingresa al Autómata de Pila puede ser aceptada o rechazada.

En la cinta de entrada de la máquina colocamos la cadena que se analizará, con la cabeza de lectura sobre la celda del extremo izquierdo de la cinta. Luego se pone en marcha la máquina desde su estado inicial, con la Pila vacía, y declaramos que la cadena se aceptará si es posible que la máquina llegue a un estado de aceptación después de leer toda la cadena-

Se usa la palabra "posible" al definir la aceptación de cadenas en un Autómata de Pila, ya que los Autómatas de este tipo son NO DETERMINISTAS.

TEOREMA: Para toda Gramática G Libre de Contexto, existe un Autómata de Pila S que acepta exclusivamente las mismas cadenas del Lenguaje L(G).

Los Autómatas de Pila pueden aceptar Lenguajes Libres de Contexto como el del ejemplo anterior. Como los Lenguajes Regulares también cumplen

con las condiciones para ser Libres de Contexto, teóricamente puede n ser manejados por Autómatas de Pila (solamente que la Pila no sería empleada en

ningún momento).

La adición de la Pila incrementa de manera considerable el potencial de procesamiento del Lenguaje de Autómata y proporciona un marco en el cual se

formulan varios algoritmos eficientes para el análisis sintáctico-

Precisamente, los analizadores sintácticos, además de los semánticos, se desarrollan principalmente a partir de Autómatas de Pila.

Victor Iván Robles Martinez

Julio 2002