PUERTA | PUERTA CS 2011 | Pregunta 65 – Part 1

Considere el lenguaje L1, L2, L3 como se indica a continuación.
L1={ | p,qN }
L2={ | p,q N y p=q}
L3={ | p, q, r N y p = q = r}

¿Cuál de las siguientes afirmaciones NO ES CIERTA ?
(A) Push Down Automata (PDA) se puede usar para reconocer L1 y L2
(B) L1 es un lenguaje normal
(C) Los tres lenguajes son independientes del contexto
(D) La máquina de Turing se puede usar para reconocer los tres lenguajes

Respuesta : (C)
Explicación: L1 es regular. Su DFA se da como

L2 no es regular, se puede probar usando el lema de bombeo (consulte a Ullman). Pero L2 es CFL.

        S → AB
        A → 0A|ε
        B → 1B|ε

L3 no es CFL, se puede probar usando el lema de bombeo (consulte a Ullman). Pero L3 es recursivo.

Cada lenguaje regular es también un CFL. Entonces PDA puede usarse para reconocer L1 y L2.
Como un lenguaje CFL y Regular es algo así como un lenguaje Recursivo. Por lo tanto, la máquina de Turing se puede utilizar para reconocer
L1, L2 y L3.
L2 no es regular, se puede probar usando el lema de bombeo (consulte a Ullman). Pero L2 es CFL.

        S → AB
        A → 0A|ε
        B → 1B|ε

L3 no es CFL, se puede probar usando el lema de bombeo (consulte a Ullman). Pero L3 es recursivo.

Cada lenguaje regular es también un CFL. Entonces PDA puede usarse para reconocer L1 y L2.
Como un lenguaje CFL y Regular es algo así como un lenguaje Recursivo. Por lo tanto, la máquina de Turing se puede utilizar para reconocer
L1, L2 y L3.

Fuente: http://clweb.csa.iisc.ernet.in/rahulsharma/gate2011key.html

Cuestionario de esta pregunta