The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+20 votes
2.4k views

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?

  1. $L_1 = \{0,1\}^*-L$
  2. $L_1 = \{0,1\}^*$
  3. $L_1 \subseteq L$
  4. $L_1 = L$
asked in Theory of Computation by Veteran (59.7k points)
edited by | 2.4k views
0
NFA in the question given wrong. It is the NFA for M1, not for M.
+3
Now it is correct diagram.
0
yes in go pdf que was wrong that's why i was confused thanks
+2
Please make appropriate corrections in GO PDF book in next edition

4 Answers

+40 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.

answered by Veteran (55.4k points)
edited by
+6
$L\subset L_1$, right?
+2
Yes.
0
Sir change the diagram
0
NFA is an incomplete system as compared to DFA which is complete.Complement exist for a DFA but not NFA.So can we complement a NFA by interchanging its final states and non final states?

pls help ?
+6 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:-  

nfa

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

answered by Loyal (8.7k points)
0
Please explain option a) too. You've explained everything else so well!
+2

Option a) isn't right.

Reason :

  • Automaton 'M' accepts string {1} also i.e. L = {1, ...}
  • {0,1}* represents {null, 0, 1, 00, 01, 10, 11,……………..}
  • {0,1}* - L removes the string {1} from the solution set, which isn't true because automaton 'M1' accepts string{1} also, i.e. L1 = {null, 0, 1, 00, 01, 10, 11,……………..}
0
applying complementation to nfa is right ???does this approach always give the write  answer???

or we need to change the nfa to dfa then complementation........clear plz??
0
What does option A actually mean?
+3 votes
L= (0+1)^+ while L1= (0+1)^* So Ans is B
answered by (249 points)
+1
How we can say L = (0+1)^+ ? NFA is not generating all the strings of (0+1)^+.
+1

sure L is not (0+1)+ as in NFA 0 is not accepting.

0 votes

@Bikram sir   What will be answer for question given in go pdf? Option C? L1is subset of L? Please confirm

answered ago by Junior (907 points)
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

44,252 questions
49,749 answers
164,070 comments
65,845 users