MATEMATICAS

TRABAJO COLABORATIVO Nº2

AUTOMATAS Y LENGUAJES FORMALES

ALEJANDRO YEPES LOPEZ

CÓDIGO 18611779

GRUPO 301405_19

TUTOR

JAIRO ARMANDO RIAÑO HERRERA

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD

CEAD – LIBANO

1.- Un Autómata a Pila define los Lenguajes Independientes del Contexto y es una extensión de los Autómatas Finitos Deterministas con transiciones ε. Sustente suficientemente porqué se afirma lo anterior.

Los Lenguajes de Contexto forman una clase de lenguajes más amplia que los Lenguajes Regulares, de acuerdo con la Jerarqu´ýa de Chomsky Estos lenguajes son importantes tanto desde el punto de vista teórico, por relacionar las llamadas Gram´aticas Libres de Contexto con los Aut´omatas de Pila, como desde el punto de vista practico, ya que casi todos los lenguajes de programación están basados en los En efecto, a partir de los a˜nos 70’s, con lenguajes como Pascal, se hizo común la practica de formalizar la sintaxis de los lenguajes de programación usando herramientas basadas en las Gram´aticas Libres de Contexto,

2.- En los Autómatas Finitos, para deducir si una cadena o palabra formada con símbolos de un Alfabeto es aceptada o no, se deduce luego de consumir toda la cadena y revisar si el estado en que quedó el autómata pertenece al conjunto de estados de aceptación o no. Describa detalladamente cómo es el proceso análogo en un Autómata a Pila.

autómata finito es un modelo matemático de una máquina que acepta cadenas de un

lenguaje definido sobre un alfabeto A. Consiste en un conjunto finito de estados y un conjunto de transiciones entre esos estados, que dependen de los símbolos de la cadena de entrada. El autómata finito acepta una cadena x si la secuencia de transiciones correspondientes a los símbolos de x conduce desde el estado inicial a un estado final.

1. Hacer una gramática independiente del contexto (G.I.C), que genere nombres de persona, mínimo un nombre y un apellido, máximo dos nombres y dos apellidos. Cada nombre y apellido debe comenzar por mayúscula.

Nota: Se tiene en cuenta que Є=vacio; no se aceptan apellidos compuestos.

nombre → nom nom2 esp nom nom2

nom2 → esp nom │Є

nom → nom min │may

may → A│B│C│D│…│Z

min → a│b│c│d│…│z

esp → “ “

Árbol de análisis sintáctico

2. Hacer una gramática independiente del contexto (G.I.C), que genere frases cuyas palabras empiecen en una vocal mayúscula y terminen en una consonante minúscula. En medio de la vocal mayúscula y la consonante pueden haber letras minúsculas.

frase → frase esp pal2│pal2

esp → “ “

pal2 → pal1 conmin

pal1 → pal2 min│vocmay

vocmay → A│E│I│O│U

min → conmin│vocmin

conmin → b│c│d│f│g│…│z

vocnim → a│e│i│o│u

3. Hacer una gramática independiente del contexto (G.I.C), que genere la sentencia condicional if con las siguientes restricciones:

* Siempre se va a comparar una variable con un número entero o una variable con otra variable.

* Los operadores relacionales son: <│>│≤│≥│==│!=

* Las variables deben empezar en una letra y después de esa letra pueden haber cualquier cantidad de números o letras.

* Los números solamente van a ser enteros de cualquier cantidad de dígitos.

* Un número no debe empezar en cero, pero puede ser cero.

* Se pueden utilizar los operadores lógicos && (and) y II (or).

* Solamente se van a utilizar los paréntesis después del

...