Question

Consider 2 scenarios:
C1: For DFA (ϕ, Ʃ, δ, qo, F),
if F = ϕ, then L = Ʃ*
C2: For NFA (ϕ, Ʃ, δ, qo, F),
if F = ϕ, then L = Ʃ*
Where F = Final states set
ϕ = Total states set
(a) Both are true (b) Both are False
(c) C1 is true, C2 is false (d) C1 is false, C2 is true

Answer 1

C1 is true.

C2 is not True but that doesn't mean it always false. C2 sometimes true some time false.

"C2: For NFA (ϕ, Ʃ, δ, qo, F), if F = ϕ, then L = Ʃ* . Where F = Final states set, ϕ = Total states set" is neither always TRUE nor always FALSE.

but even one case contradict then it considered as false. so answer is Option C.

Comments

can you mention for which case its false

---

let input alphabet is a,b..

and let an NFA with S0 as single starting andfinalstate without any transition.. language accepted by this NFA is epsilon. (making all state as final doesn't make any sense here).

so language accepted by this NFA is epsilon not (a+b)* i.e. sigma star.

---

okay sir that's fine that no transition is defined on S0 but if transition is not defined for any input then there will be dead configuration at s0 if any input came so nfa remains halt at s0 which is infact a final state. Therefore, L must be (a + b)^*. Correct me if i am wrong

---

^^  transition not given, does it mean it is self loop of every input symbol ???

---

are you talking about nfa with null transitions?

---

Sorry, i was wrong......messed up with halting and non halting TM, need to revise toc. One of the easiest quest it was :-p. Anyways thanx.

---

I did not understand what case u r explaining. u are defining input symbol as {a,b} and not considering it in your nfa. please elaborate the explanation.

---

Here in C1.how is epsilon accepted

L closure means it should have epislon too.

is it covered by the fact,that start symbol is also a final state,so wthout any input I am reaching a final state?

Plz clarify @Digvijay

---

@Gate Mm

when all states are final states, it mean start state is also final states, $\epsilon$ will be there in DFA/NFA

---

Sir for DFA also If I dont make any transition then also , I will have the same criteria as accepting only ϵ

ϵ∈, so then why is C2 false , I am not getting the logic clearly ,plz clarify it again .

---

In DFA we have transitions for all symbols and all states are final states, so all strings will be accepted.

In NFA, there may be some symbols for which there is no transition. then all strings will not be accepted.

---

Very appropriate. If transition is not defined then it becomes undefined and hence, false in that case.

Answer 2

C1 is true and C2 is false.

Comments

In case of a NFA even if F = ϕ, there may be some states where we have no transitions defined for a particular symbol i.e Dead state rejections in NFA. Due to which, L ≠ Ʃ*.however this is not the case for dfa here

Answer 3

C1 is true, C2 is false

As in case of NFA even is F = ϕ, dead state rejection is there so L ≠ Ʃ* .