Theory of computation

Question

No of State for minimal DFA for empty language ?

If your answer is 1 or 2 then please explain to support your answer

Answer 1

Only one state is required. And it will be the starting state, all transitions go from this state to itself. And there will be no final state.

Comments

Minimal DFA batao ...... And IIT professors say it requires 2 state and without finial state we can't make minimal DFA. There words ..... And difine your answer on the basis of Myhill nearod theorem

---

@Abhi Som Can you tell me where you read IIT professor saying this?? Any link to the lecture or notes?

---

Please explain with Myhill nearod theorem ..... This theorem explain minimal DFA .... I have a frd he told me ..... But he can't explain .... He is in IIT Bombay...

---

as per definition of DFA, Final states $F \subseteq Q,$ i.e, that may be empty set.

---

Minimal ki baat ho Rahi he ...... 2 state we banayenge tab bhi F is proper subset of Q ... 3 se banayenge tab bhai....  F⊆Q is irrelevant ..... Myhill define minimal DFA .... Give your answer based on that ....

---

In the theory of formal languages, the Myhill–Nerode theorem provides a necessary and sufficient condition for a language to be regular.

-Wikipedia

This theorem is used for proving if a language is regular or not.

---

@abhi ,

design any dfa with any no of states for language L={ } with/without final state , (if there is any final state in dfa for L={ }, then that will be either unreachable from start state or L is non empty  ,then unreachable states need to remove from dfa to minimize), then apply myhill-nerode to find equivalence states.

---

Pura pado .... Wikipedia pe .... No of equivalence class on set (language L) is equal to the states in minimal DFA of L ...

---

@praveen .... If one state used to create minimal DFA of empty language then there have to be one equivalence class ..... True... Then empty language have to follow equivalence relation .... But it don't.... It is not reflexive...

Answer 2

One non-final state, which will also act as start state and transitions of that state from the specified input symbols to itself.

Comments

Bhavana, AAP saare comments padho....