Automatas

Solo disponible en BuenasTareas
  • Páginas : 2 (382 palabras )
  • Descarga(s) : 0
  • Publicado : 4 de septiembre de 2012
Leer documento completo
Vista previa del texto
UNIVERSIDAD INDUSTRIAL DE SANTANDER Autómatas y Lenguajes Formales -2o Examen - Grupo D1 - 27/Jul/2011 Profesor: Luis Eduardo Zambrano Fz
Todos los numerales tienen igual valor

1. Considere elsiguiente NFA sobre el alfabeto {x, y} con estado inicial S y estado de aceptación V

a) ¿Cuál de las siguientes expresiones regulares corresponde al autómata anterior? i. xxx ∪ yyx ii. x3 y 2 x ∗ ∗iii. x y x iv. xx∗ (x ∪ y)y ∗ x ∗ ∗ v. x xy x b) ¿Cuál de las siguientes gramáticas sobre el alfabeto {x, y} genera el lenguaje reconocido por el autómata anterior? i. S −→ xT x T −→ xU y | yU y U −→xV S −→ xT | T T −→ xT | xU | yU | T | U U −→ yU xV V x S −→ xT T −→ xT | T U −→ yU | V V −→ xV | x ii. S −→ xT T −→ xT | xU | yU U −→ yU | xV S −→ xT T −→ xT | yU U −→ yU | xV S −→ xT T −→ xT | xU |yU U −→ yU | x

iii.

iv.

v.

vi.

2. Minimar1 los siguientes autómatas de estado finito

(a)
1 Esto

(b)

es, encontrar un DFA con la menor cantidad de estados que reconozca el mismolenguaje.

1

3. Nociones básicas de la Teoría de Autómatas y Lenguajes Formales. a) Complete la siguiente tabla basado en la Jerarquía de Chomsky Tipo 0 1 2 3 Lenguaje Autómata Gramática

b)Defina los siguientes términos i. iii. v. Forma sentencial Lenguaje libre del contexto Lenguaje libre del contexto ambiguo ii. iv. Gramática libre del contexto Gramática ambigua

4. Para cada uno delos siguientes lenguajes sobre el alfabeto Σ = {a, b, c}, construir una gramática libre del contexto que los genere. a) L1 = {c, ab} ∪ {am bm an bn | m, n ≥ 1} b) L2 = {a2m bn+3m c3n | m, n ≥ 0} 5.Convierta la siguiente gramática libre del contexto a la Forma Normal de Chomsky S −→ aY | Y bb | Y X −→ | a Y −→ aXY | bb | XXa 6. Use el lema del bombeo para lenguajes regulares para mostrar que ellenguaje n! L = {a | n ≥ 0} sobre el alfabeto Σ = {a} no es regular. 7. Use el lema del bombeo para lenguajes libres del contexto para mostrar que el lenguaje p L = {1 | p es un número primo} sobre el...
tracking img