PUERTA | PUERTA-CS-2003 | Pregunta 55

Considere el NFA M que se muestra a continuación.

Sea L el lenguaje aceptado por M. Sea L1 el lenguaje aceptado por NFA M1, obtenido al cambiar el estado de aceptación de M a un estado de no aceptación y al cambiar el estado de no aceptación de M a estados de aceptación. Cuál de las siguientes afirmaciones es verdadera ?
(A) L1 = {0, 1}* – L
(B) L1 = {0, 1}*
(C) L1 ⊆ L
(D) L1 = L

Respuesta: (B)
Explicación:

In case of a Deterministic Finite Automata (DFA) when we change 
the accepting states into non-accepting states and non-accepting 
states into accepting states, the new DFA obtained accepts the complement
of the language accepted by the initial DFA. It is because we have one 
single movement for a particular input alphabet from one state so the strings
accepted by the transformed DFA will be all those which are not accepted by 
the actual DFA. 

But it is not the case with the NFA’s (Non-Deterministic Finite
Automata). In case of NFA we need to have a check on the language accepted by the 
NFA. The NFA obtained by changing the accepting states to non-accepting states and 
non-accepting states to accepting states is as follows:-  

Here we can see that as 
i.  The initial state is an accepting state hence null string is always accepted by 
    the NFA.
ii. There is a movement from state 1 to state 2 on both {0, 1} input alphabets and 
    further any  number of 1’s and 0’s or even none in the string lets the string be 
    at an accepting state(state 2).

Hence the language accepted by the NFA can be any string with any combination of 0’s 
and 1’s including a null string i.e. {null, 0, 1, 00, 01, 10, 11,……………..} so L1= {0, 1}*.

Esta explicación ha sido aportada por Yashika Arora.

Cuestionario de esta pregunta