PUERTA | PUERTA CS 2013 | Pregunta 33

Considere el DFA dado.

¿Cuáles de las siguientes son FALSAS?

1. Complement of L(A) is context-free.
2. L(A) = L((11*0+0)(0 + 1)*0*1*)
3. For the language accepted by A, A is the minimal DFA.
4. A accepts all strings over {0, 1} of length at least 2. 

(A) 1 y 3 solamente
(B) 2 y 4 solamente
(C) 2 y 3 solamente
(D) 3 y 4 solamente

Respuesta: (D)
Explicación: 1 es verdadero. L(A) es regular, su complemento también sería regular. Un lenguaje regular también está libre de contexto.

2 es cierto.

3 es falso, el DFA se puede minimizar a dos estados. Donde el segundo estado es el estado final y llegamos al segundo estado después de un 0.

4 es claramente falso ya que DFA acepta un solo 0.

Cuestionario de esta pregunta