edited by
2,321 views
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

(a) {w ∈ Σ* : δ*(q0,w) ∩ (Q-F) ≠ Φ)?

(b) {w ∈ Σ* : δ*(q0,w) ∈ (Q-F))?

edited by

1 Answer

1 votes
1 votes
In general for complement of l(M) :
1. {w ∈ Σ* : δ*(q0,w) ∩ F = Φ) is true for NFA

2. {w ∈ Σ* : δ*(q0,w) ∉ F)) is true for DFA

For your given problem,

(a) {w ∈ Σ* : δ*(q0,w) ∩ (Q-F) ≠ Φ)} doesn't hold good for NFA

Since, statement doesn't guarantee that string doesn't reach the final state it only says that "There will be at least one such case where string will reach to non-final state" whereas

(b) {w ∈ Σ* : δ*(q0,w) ∈ (Q-F)} holds good for NFA

Since it guarantees that all the strings will reach to non-final states only !

Correct me if I am wrong.

edited by

Related questions

0 votes
0 votes
0 answers
1
0 votes
0 votes
0 answers
2
1 votes
1 votes
0 answers
3
0 votes
0 votes
0 answers
4