Teoría de autómatas | Serie 1

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

1. Sean S y T lenguaje sobre ={a,b} representado por las expresiones regulares (a+b*)* y (a+b)*, respectivamente. ¿Cual de los siguientes es verdadero? (GATE CS 2000)

(a) ScT (S es un subconjunto de T)
(b) TcS (T es un subconjunto de S)
(c) S=T
(d) SnT=Ø

Respuesta: (c).

2. Sea L el lenguaje generado por la gramática S – OSO/00. ¿Cual de los siguientes es verdadero? (GATE CS 2000)
(a) L = O
(b) L es regular pero no O
(c) L es independiente del contexto pero no regular
(d) L no es independiente del contexto

Respuesta: (b)
Explicación: tenga en cuenta que la gramática en sí no es regular, pero el lenguaje L es regular, ya que L se puede representar usando una gramática regular, por ejemplo, S -> S00/00.
Referencias:
http://en.wikipedia.org/wiki/Regular_grammar

3. Considere las siguientes dos afirmaciones:
S1: { 0^2n |n >= l} es un idioma regular
S2: { 0^m 0^n 0^(m+n) lm >= 1 and n >= 2} es un idioma regular
¿Cuál de las siguientes afirmaciones es correcta? (GATE CS 2001)
a) Solo S1 es correcto
b) Solo S2 es correcto
c) Tanto S1 como S2 son correctos
d) Ninguno de S1 y S2 es correcto

Respuesta: (c)
Explicación:
S1 se puede escribir como (00)^n donde n >= 1. Y S2 se puede escribir como (00)^(m+n) donde m >=2 y n >= 1. S2 se puede reducir aún más a (00)^x donde x >= 3.
Podemos escribir fácilmente gramáticas regulares tanto para S1 como para S2.
G1 -> G100/00 (para S1)
G2 -> G200/000000 (para S2)

4. ¿Cuál de las siguientes afirmaciones es verdadera? (GATE CS 2001)
(a) Si un idioma es libre de contexto, siempre puede ser aceptado por un autómata determinista push-down
(b) La unión de dos idiomas libres de contexto es libre de contexto
(c) La intersección de dos idiomas libres de contexto es libre de contexto
(d) El complemento de un lenguaje libre de contexto es libre de contexto

Respuesta: (b)
Explicación:
Los lenguajes libres de contexto se cierran bajo las siguientes operaciones. Es decir, si L y P son lenguajes libres de contexto y D es un lenguaje regular, los siguientes lenguajes también son libres de contexto:
• la estrella Kleene L * de L
• la imagen Ø(L) de L bajo un homomorfismo Ø
• la concatenación de L y P
• la unión de L y P
• la intersección de L con un lenguaje regular D (L n D).
Los lenguajes independientes del contexto no se cierran bajo el complemento, la intersección o la diferencia.
¿Por qué a) no es cierto?
El lenguaje reconocido por el autómata pushdown determinista es un lenguaje libre de contexto determinista. No todos los lenguajes libres de contexto son deterministas. Esto es diferente a la situación de los autómatas finitos deterministas, que también son un subconjunto de los autómatas finitos no deterministas pero pueden reconocer la misma clase de lenguajes (como lo demuestra la construcción del subconjunto).
Referencias:
http://en.wikipedia.org/wiki/Context-free_language
http://en.wikipedia.org/wiki/Deterministic_pushdown_automaton

5. Dado un autómata finito no determinista arbitrario (NFA) con N estados, el número máximo de estados en un DFA minimizado equivalente es al menos. (GATE CS 2001)
(a) N^2
(b) 2^N
(c) 2N
(d) N!

Respuesta: (b)
Referencias:
http://en.wikipedia.org/wiki/Powerset_construction