The Gateway to Computer Science Excellence

+28 votes

Consider the NFA $M$ shown below.

Let the language accepted by $M$ be $L$*. *Let $L_1$* *be the language accepted by the NFA $M_1$ obtained by changing the accepting state of $M$ to a non-accepting state and by changing the non-accepting states of $M$ to accepting states. Which of the following statements is true?

- $L_1 = \{0,1\}^*-L$
- $L_1 = \{0,1\}^*$
- $L_1 \subseteq L$
- $L_1 = L$

+51 votes

Best answer

Answer is **B** .

As the problem said:

As in above **NFA** language $L_1$ is $\{0,1\}^*$ . [we don't know $L$, we need not to find out]

**Option A** is wrong as $L$ is accepting $1$ and $L_1$ is also accepting $1$

**Option C** is wrong as $L_1$ accepting ^,null, but $L$ is not .

**Option D **is wrong for same reason as option C is wrong.

+10 votes

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}*.

So,answer is B

+4

*Option a) *isn't right.

**Reason : **

- Automaton 'M' accepts string {1} also i.e.
*L = {1, ...}* represents*{0,1}***{null, 0, 1, 00, 01, 10, 11,……………..}*removes the string {1} from the solution set, which isn't true because automaton 'M1' accepts string{1} also, i.e.*{0,1}* - L**L1 = {null, 0, 1, 00, 01, 10, 11,……………..}*

+3 votes

0 votes

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.6k
- Digital Logic 2.9k
- Programming and DS 5k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.2k
- Databases 4.2k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.5k
- Others 2.1k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

51,925 questions

58,832 answers

200,156 comments

111,916 users