Scribd
Cargar
76 vistas2 páginas

IUA IS AyLF ActividadObligatoria U1 PDF

El documento presenta 6 gramáticas formales y solicita clasificarlas según los tipos de Chomsky, obtener los lenguajes mediante árboles sintácticos y derivaciones sucesivas, e identificar gramáticas ambiguas o equivalentes.

Cargado por

Cristian Raful
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd
76 vistas2 páginas

IUA IS AyLF ActividadObligatoria U1 PDF

El documento presenta 6 gramáticas formales y solicita clasificarlas según los tipos de Chomsky, obtener los lenguajes mediante árboles sintácticos y derivaciones sucesivas, e identificar gramáticas ambiguas o equivalentes.

Cargado por

Cristian Raful
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd

FUERZA AÉREA ARGENTINA

INSTITUTO UNIVERSITARIO AERONÁUTICO


F.C.A. – CARRERA DE INGENIERÍA DE SISTEMAS

GUIA DE ACTIVIDADES PRÁCTICAS

ASIGNATURA: Autómatas y Lenguajes Formales Año académico : 2013


ÁREA: Tecnologías Básicas BLOQUE: Programación Año: 4º Semestre: VIII
Total Hs: 80 Teórico: 32 Práctico: 48 For. Exp.: --- Prob. Ing.: 12 Proy. y D.: ---

Actividad No.: 1 Denominación: Autómatas y Máquinas Secuenciales


Carga horaria: 15 Tipo de actividad: Form.Exp. Problema Ing. Proyecto y Dis.
Carácter: obligatoria Realización: individual Plazo de entrega: 5 días

Unidad / Contenidos: Unidad 1 – MÁQUINAS, LENGUAJES Y GRAMÁTICAS FORMALES

 Concepto de reglas de producción


 Gramáticas Formales: Definiciones
 Tipos de Gramáticas: Clasificación de Chomsky
 Árboles de derivación sintáctica
 Conceptos de Ambigüedad y Recursividad

Objetivos de aprendizaje:

 Identificar una Gramática y sus componentes.


 Identificar el tipo de Gramática según la clasificación de Chomsky.
 Obtener el lenguaje que genera una Gramática a través de Derivaciones y Arboles
Sintácticos.

Actividades a ser desarrolladas:

Para cada una de las gramáticas siguientes se pide:


a) Clasifica cada una según los tipos de Chomsky
b) Obtiene el Lenguaje de la gramática tipo 3 mediante árboles sintácticos
c) Obtiene el Lenguaje de la gramática tipo 2 mediante derivaciones sucesivas
d) Si existen gramáticas ambiguas, indica cuales y demuestra las derivaciones correspondientes
e) Si existen gramáticas equivalentes, indica cuales y demuestra mediante las derivaciones
correspondientes

1) S:= bBb | bAa 2) S:= aA 3) S:= cA


bAa:= bBa | bba Aa:= bC | aacC A:= aC | bB
bBb:=bbbb | bab cC:= ca |c B:= bC | a
C:= b | c | a

4) S:= BAa 5) P:= bQb | bba | bab 6) S:= aaA


A:= Ca | a bQb:= bRb A:= aa | aaB |cB
B:= Ab | c bRb:= bSb B:= b | bC
C:= ab bSb:= bbbb C:= c | 

1
FUERZA AÉREA ARGENTINA
INSTITUTO UNIVERSITARIO AERONÁUTICO
F.C.A. – CARRERA DE INGENIERÍA DE SISTEMAS

GUIA DE ACTIVIDADES PRÁCTICAS

Observaciones y otras indicaciones:

Presentar la solución de los ejercicios en algún formato.

Resultados a presentar y modalidad:

La presentación es individual.

También podría gustarte