1 votes 1 votes Is it true that for every nfa M = (Q, Σ,δ,q0,F)the complement of L (M)is equal to the set {w ∈ Σ* : δ*; (q0,w) ∈ (Q – F) = Ø}? If so, prove it; if not, give a counterexample. plz explain this ques by taking some simple example ANJALI SAWARKAR asked Jul 29, 2017 ANJALI SAWARKAR 330 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes It seems true what you mentioned in the question. The complement of a language accepted by an FA will be, subtract all strings accepted by that FA from Sigma*. Lc = {w ∈ Σ* :δ*; (q0,w) ∈ (Q – F) = Ø} it means we are considering all those strings from Sigma* which will not be accepted by this NFA, and this only is the definition of complement of a machine. PS: I think in quesiton it should be Q INTERSECTION F = Phi Manu Thakur answered Jul 29, 2017 • edited Jul 30, 2017 Manu Thakur comment Share Follow See all 0 reply Please log in or register to add a comment.