Scribd
Cargar
4 vistas3 páginas

Práctica 1: Ambigüedad en Gramáticas Libres de Contexto: Objetivos

La práctica se centra en analizar una gramática libre de contexto para determinar su ambigüedad mediante métodos teóricos y computacionales. Se identificaron derivaciones y se construyeron árboles de derivación para la cadena 'abab', confirmando su ambigüedad a través de un programa en Python. Los resultados muestran que la gramática permite múltiples estructuras sintácticas para la misma cadena, lo que es crucial para el diseño de analizadores sintácticos.

Cargado por

finanzasdieg103
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
4 vistas3 páginas

Práctica 1: Ambigüedad en Gramáticas Libres de Contexto: Objetivos

La práctica se centra en analizar una gramática libre de contexto para determinar su ambigüedad mediante métodos teóricos y computacionales. Se identificaron derivaciones y se construyeron árboles de derivación para la cadena 'abab', confirmando su ambigüedad a través de un programa en Python. Los resultados muestran que la gramática permite múltiples estructuras sintácticas para la misma cadena, lo que es crucial para el diseño de analizadores sintácticos.

Cargado por

finanzasdieg103
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

Práctica 1: Ambigüedad en Gramáticas Libres de

Contexto
Teoría de la Computación

Objetivos
Objetivo general
Analizar una gramática libre de contexto con el propósito de determinar si es ambigua,
utilizando métodos teóricos y computacionales.

Objetivos específicos
Identificar las producciones de una gramática libre de contexto.

Generar derivaciones para una misma cadena.

Construir árboles de derivación.

Verificar la ambigüedad de la gramática mediante un programa en Python.

Interpretar los resultados obtenidos de manera formal.

Material utilizado
Computadora personal.

Lenguaje de programación Python 3.

Editor de texto o entorno de desarrollo (Visual Studio Code o similar).

Intérprete de Python.

Conocimientos de gramáticas libres de contexto y teoría de la computación.

Documento de la práctica proporcionado por el docente.

1
Desarrollo
Se analizó la gramática libre de contexto:

S → aSb | bSa | SS | λ
En primer lugar, se realizó un análisis teórico de la gramática, observando que la pro-
ducción SS permite concatenar derivaciones, lo cual es un indicio de ambigüedad. Poste-
riormente, se seleccionó la cadena abab, la cual puede generarse mediante dos derivaciones
distintas.
Ambas derivaciones producen la misma cadena final, pero con estructuras sintácticas dife-
rentes, lo que se comprobó mediante la construcción de árboles de derivación. Finalmente, se
implementó un programa en Python que genera cadenas a partir del símbolo inicial y contabi-
liza el número de derivaciones por cadena, confirmando computacionalmente la ambigüedad
de la gramática.

Tablas
Derivaciones de la cadena abab
Derivación Pasos principales
1 S ⇒ aSb ⇒ aSSb ⇒ abSab ⇒ abab
2 S ⇒ SS ⇒ aSbS ⇒ abS ⇒ abab

Resultado del programa en Python


Cadena Número de derivaciones
abab 2

Gráficas
En esta práctica no se generaron gráficas numéricas, ya que el análisis se centra en estruc-
turas formales. Sin embargo, los árboles de derivación cumplen la función de representaciones
gráficas del proceso de generación de cadenas, permitiendo visualizar la ambigüedad de la
gramática.

Conclusiones
La gramática analizada es ambigua, ya que existe al menos una cadena que puede
generarse mediante más de un árbol de derivación.

La ambigüedad se comprobó tanto de manera teórica como computacional.

El uso de programación facilitó la verificación automática de los resultados.

2
El estudio de gramáticas ambiguas es fundamental para el diseño de analizadores sin-
tácticos y compiladores.

También podría gustarte