why dead state? I havenot understand this point

The Gateway to Computer Science Excellence

+3 votes

Best answer

Answer will be 3 assuming that $\Sigma = \{ a\}$ Or It will be $4$ if $\Sigma \supset \{ a \} $

The language $L = \Sigma^* - \{ \in,a\}$

If $\Sigma = \{ a\}$ then the Minimal DFA would look like the following :

If $\Sigma \supset \{ a \} $ then Minimal DFA will look like the above but with one Dead State extra.

0

I have one doubt, why the above language is not

L={a2,a3,a4,a6,a8.......} So that the states in minimal dfa is 6

L={a2,a3,a4,a6,a8.......} So that the states in minimal dfa is 6

0

coz it is not n=2m ...it is n > =2m and m>=1

so any string greater than or equal to size 2 is accepted.

Also $n=3$ is of no use here.

so any string greater than or equal to size 2 is accepted.

Also $n=3$ is of no use here.

+1

depends on whether only $a$ is there as an input string or $\{a,b,....\}$ are there in the input set.

dead state will be required to show transition on inputs other than $a$.

like when $b$ is given as input then it should lead to dead state.

dead state will be required to show transition on inputs other than $a$.

like when $b$ is given as input then it should lead to dead state.

0

@ Satbir yeah thanks I did not notice n>=2m(greater than sign), but if n=2m where m>=1 or n=3 then minimal dfa would have 6 states right?

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.4k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.4k
- Others 1.7k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,654 questions

56,169 answers

193,876 comments

94,298 users