The Gateway to Computer Science Excellence
0 votes
119 views

How many number of $DFA$ states(minimal DFA) required which accepts the language $L=\left \{ a^{n}:n=\text{3 or n>= 2m for all m>= 1} \right \}$ ___________


Answer will be $3$ or $6?$

in Theory of Computation by Veteran (117k points)
edited by | 119 views

1 Answer

+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. 

by Boss (26.1k points)
selected by
0
why dead state? I havenot understand this point
+1
I think he means if the number of input symbol is >1 then we will need a dead state.
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
0

@codingo1234

why 6 states??

is this language accepts $a^{5}?$

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.
0

@Satbir

So, no dead state required. right??

+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.
0

 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?

+1
yes

$*$ represents the final state.

$\rightarrow A\overset{a}{\rightarrow}B\overset{a}{\rightarrow}C^*\overset{a}{\rightarrow}D^*\overset{a}{\rightarrow}E^*\overset{a}{\leftrightarrow}F$
0
thanks bro

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,654 questions
56,169 answers
193,876 comments
94,298 users