Programacion

|
|
|
|
|
|
|
|

INTRODUCCION A LOS LENGUAJES FORMALES

DANIELA MONDRAGON ROSAS

MATEMATICAS PARA COMPUTACION

INSTITUTO TECNOLOGICO DE TLALNEPANTLA

SEGUNDO SEMESTRENo de Control: 09250841
31 de julio de 2010

1. En cada uno de los siguientes incisos determina si la gramatca dada es regular, libre de contexto y/o sensible al contexto. Especifica turespuesta.
a) Sea:
T={x,y,z} N={s,A,B,C}
Composiciones:
sxs AxA BxA CxC Cy
Es sensible alcontexto por tener menos símbolos del lado izquierdo que en el lado derecho.
sxB AyC ByC CzA Ay
Es libre del contextoporque del lado izquierdo hay solo un símbolo no terminal (N) y del lado derecho hay dos símbolos, uno terminal (T) y el otro no terminal (N).
syA AzB BzsCyB sz
Es regular porque del lado izquierdo hay solo un símbolo terminal y del lado derecho hay dos símbolos, uno terminal (T) y el otro es no terminal (N).
b) Sea:T={x,y,z} N={s,A,B}
Composiciones:
syA AxBA BBx
BxAAzB xAzCB BAyy
Ayz CyzzBxx
Sus composiciones son sensibles al contexto, libres de contexto y regulares excepto una que es diferente a las demás por la cantidad de símbolos que tiene de cada lado,entonces seria de tipo 0 porque no tiene restricciones y formaría parte de la gramática.
c) Sea:
T={x,y} N={s,A,B}
Composiciones:
sxB ByxCCBxA
AxBy ByyC Cxy
ACBx Bx Ay
Estas composiciones son de los tres tipos: libre del contexto, sensible...