Teoría de autómatas | conjunto 3

Se han hecho las siguientes preguntas en el examen GATE CS 2011.

1) ¿El análisis léxico para un lenguaje moderno como Java necesita el poder de cuál de los siguientes modelos de máquina en un sentido necesario y suficiente?
(A) Autómatas de estado finito
(B) Autómatas pushdown deterministas
(C) Autómatas pushdown no deterministas
(D) Máquina de Turing

Respuesta (A)
El análisis léxico es el primer paso en la compilación. En el análisis léxico, el programa se divide en tokens. Los analizadores léxicos se basan típicamente en autómatas de estado finito. Los tokens normalmente se pueden expresar como diferentes expresiones regulares:
un identificador viene dado por [a-zA-Z][a-zA-Z0-9]*
La palabra clave if viene dada por if.
Los números enteros están dados por [+-]?[0-9]+.

2) ¿Cuáles de los siguientes pares tienen DIFERENTE poder expresivo?
(A) Autómatas finitos deterministas (DFA) y autómatas finitos no deterministas (NFA)
(B) Autómatas de empuje hacia abajo deterministas (DPDA) y autómatas de empuje hacia abajo no deterministas
(C) Máquina de Turing de cinta única determinista y cinta única no determinista Máquina de Turing
(D) Máquina de Turing de una sola cinta y máquina de Turing de varias cintas

Respuesta (B)
DPDA no puede manejar lenguajes o gramáticas con ambigüedad, pero NDPDA puede manejar lenguajes con ambigüedad y cualquier gramática libre de contexto.

3) A continuación se proporciona una automatización finita determinista (DFA)D con el alfabeto ∑= {a,b}. ¿Cuál de las siguientes máquinas de estados finitos es una DFA mínima válida que acepta el mismo lenguaje que D?

Respuesta (A)
Las opciones (B) y (C) no son válidas porque ambas aceptan ‘b’ como una string que no acepta give DFA. D no es válido porque acepta bb+a que DFA no acepta.

Consulte GATE Corner para ver todos los documentos/soluciones/explicaciones del año anterior, programa de estudios, fechas importantes, notas, etc.

Escriba comentarios si encuentra que alguna de las respuestas/explicaciones es incorrecta, o si desea compartir más información sobre los temas discutidos anteriormente.