Postal Book Course

Question

Q : Let M= (Q, ∑, δ, S, F) and M’= (Q, ∑, δ, S, Q – F) where M accepts L and M’ accepts L1 and M is NFA, what could be the relation between L and L’ ?

(a) L and L’ are complement to each other

(b) L and L’ are similar to each other

(c) L and L’ relation cannot be predicted

(d) None of the above

Comments

Yes, I missed that. You're right. Thanks.

---

question is asking comparison between L and L' (L complement) whereas L1 is the language accepted by the NFA.

So it is complement only mostly  but still not sure.

---

Alright so here's what I think. First, the question should be L1 or L' throughout I think that's a typo. I'll assume it's L'.

Now, they haven't mentioned that L' is complement of L (just because it has a " ' " doesn't mean it's complement unless specified. There was a similar question asked in ISRO some time back. )

Now M and M' are two machines which may not produce complemented languages because they are NFA's. M accepts L and M' accepts L'. So you can't really say if L and L' are complements. To make it more clear replace L' with L1 throughout the question.

Answer 1

​​​​​​C) L and L’ cannot be predicted.

   because compliment of NFA is doesn’t means compliment of langugae.

 for eg. L = {starting with “a” over {a,b}}  

        it L’ = { ϵ, b, ba,bba,baaa,baab …...}

  let M is NFA for L then M’  is not an NFA for L’ it may be sometimes in other example.