Ingeniería en Sistemas de la Información y Ciencias de la Computación

Universidad Mariano Gálvez de Guatemala

Centro Regional Cuilapa, Santa Rosa

Facultad de Ingeniería en Sistemas.

Carrera: Ingeniería en Sistemas de la Información y Ciencias de la Computación

Curso: Lenguajes Formales y Autómatas

Código: 1590-028

Catedrático: Ing. Julio Cesar Escobar.

Tema:

Preguntas segundo parcial

Nombre: Gerson Isai Gutierrez Pèrez

Carné: 1590-17-23391

Sección: A

Semestre: 6th

Barberena, 27 de septiembre del 2019

1. Describa la jerarquía de chowky.

[pic 1]

Esta descripción encaja con los dispositivos automáticos de cómputo entonces existentes. Así, los lenguajes regulares con el autómata finito, los libres del contexto con el autómata dotado de una pila de memoria, mientras que el concepto de lenguaje recursivamente enumerable coincide exactamente con los lenguajes reconocidos por una máquina de Turing. Posteriormente, los lenguajes sensibles al contexto se identificaron con una máquina de Turing con memoria acotada en función del tamaño de la palabra a reconocer.

1. ¿Qué es una gramática independiente de contexto?

Una gramática independiente del contexto (GIC) es una gramática formal en la que cada regla de producción es de la forma:  Exp → x

Donde Exp es un símbolo no terminal yx es una cadena de terminales y / o no terminales. El término independiente del contexto se refiere al hecho de que el no terminal Exp puede siempre ser sustituido por x sin tener en cuenta el contexto en el que ocurrió. Un lenguaje formal es independiente de contexto si hay una gramática libre de contexto que lo genera, este tipo de gramática fue creado por Backus-Naur y se utiliza para describir la mayoría de los idiomas de programación.

1. ¿Cuáles son las partes de una G.I.C?

1. Símbolos terminales (elementos que no móviles nada)

2. Sin terminales (elementos del lado izquierdo de una producción, antes de la flecha "->")

3. Producciones (sentencias que se escriben en la gramática)

4. Símbolo inicial (primer elemento de la gramática)

1. Indique la G.I.C de a*b

S->Ab

A->aA

A-> vacia

1. Indique la G.I.C para b+ (a I b)* b

S - ABb

A - b/bA

B- aB / bB / E

1. ¿Cuáles son los simbolos inútiles, explique y ejemplifique?

1. No generadores.
2. No alcanzables: Un símbolo auxiliar que nunca se podrá alcanzar desde el símbolo inicial de la gramática es un símbolo no alcanzable, esto es, un símbolo que nunca aparecerá en la derivación de una cadena:
3.  S → Aab | B | b
4. A → aA | a | aBAE
5. B → bB | F | λ
6.  E → aaE | bB
7.  F → aF | ab

c. Producciones unitarias: Las producciones de la forma A → B dan lugar a trabajo innecesario, ya que cuando aparecen enuna derivacion lo ´ unico que introducen es un cambio de nombre del auxiliar. Por eso tambi ´ en se eliminan ´cuando se pretende obtener una gramatica simplificada.

1. Producciones vacías: una gramatica contiene producciones vacías, por ejemplo A → λ, y en el proceso de generacion de una cadena aparece el sımbolo A en un forma sentencial, esto quiere decir que, mas pronto o  mas tarde, el auxiliar A va a ser substituido por ´λ. Esto no supone un “avance” en el proceso de generar la cadena ya que substituir A por λ es lo mismo que eliminar A y, entonces ¿que utilidad ha reportado el ´ uso del auxiliar A en el proceso? Ninguna, y de hecho lo hemos “eliminado” al substituirlo por λ.

1. ¿Qué es una recursividad en una G.I.C y que tipos existen?

Permite expresar iteración utilizando un número pequeño de reglas de producción. Una gramática se dice que es recursiva si en una derivación de un símbolo no-terminal aparece dicho símbolo en la parte derecha:

A => aAb

• Tipos de recursividad:

– por la izquierda: Problemática para el análisis descendente, funciona

bien en los analizadores ascendentes.

A => Ab

– por la derecha: Utilizada para el análisis descendente.

A => aA

– por ambos lados: No se utiliza porque produce gramáticas ambiguas

1. ¿Qué es factorización en una G.I.C coloque un ejemplo.

el método de factorización lo quepermite es una transformación gramatical útil para el análisis sintáctico de tipo predictivo. Esto ocurre cuando se tienen dos producciones alternativas para un mismo n termina y no sé sabe cual de ellas utilizar para ampliarlo. Un ejemplo que permite visualizar este problema es el representado por las producciones:

A  αβ1 | αβ2 = A  αβ1

 A  αβ2

Para resolver este problema se plantea un algoritmo general de factorización, este recibe una gramática, y produce como salida una gramática factorizada por la izquierda. Consiste en tomar cada no terminal

igual, sea A el no terminal del ejemplo planteado, y encontrar el prefijo más largo que esté presente en todas las producciones para A.

1. ¿Qué es derivar?¿Qué tipos de derivación hay?

Una derivación es una secuencia de cadenas de símbolos (llamadas formas senténciales) en la que cada cadena es resultado de la aplicación de una regla de la gramática a la cadena anterior. Una derivación valida es aquella en la que la primera cadena de la secuencia es el símbolo inicial, y la ´ultima es una cadena de terminales.

...