in Theory of Computation
1,544 views
2 votes
2 votes
I know that for L={a^n, n>=0}, there would be 2 states in DFA because there is no restriction on the value of n. However, what would be the no of states when n is restricted to a finite value, such as 1000 or 10000? And how feasible would it be to construct such a DFA?
in Theory of Computation
1.5k views

4 Comments

Because one state would be for dead state, when a 'b' is encountered..I am sorry I did not specify the input alphabet..if input alphabet is {a,b} then 2 states and if input alphabet is {a} then 1 state.
0
0
yup then fine but still 1001 states will be required  if      0 <= n <= 1000   considering alphabet {a,b}
0
0
@sumit goyal 1 We will have string length + 2 right? n+1 to cover string length and 1 more for reject.
0
0

2 Answers

0 votes
0 votes

According to the above problem, the language defines as L={ an / n$\succeq$0}, for the single input alphabet a.

The above language generate 0 or more occurance of a such as {$\epsilon$,a,aa,aaa,aaaa,aaaaa............}

The RE for language is a*   which means MDFA contain 1 state.

Now suppose when n is restricted to finite value such as n =5,  for such type of language is as follow

L={an/0$\preceq$n$\preceq$5}

which accept all string of a length less than equal to 5 including $\epsilon$}

the last valid string for such type of language is "aaaaa", after that all strings are invalid goes to the dead state.

Likewise you can calculate the number of state for large number such as 1000,10000 etc.

–1 vote
–1 vote
As per the question, the language can be considered as which accepts the string that contains 0 or more 'a'.

So, the number of states will be 2 whatever the value of n may be.

One state accepts the input 'a' and the other to reject the string which contains 'b'.

3 Comments

Why are you taking input alphabet b.
1
1
no of states will be 1

but according to question suppose if n=1000

then will it determine, if it accepts 1 string or 2 string or 1000 string?

how to guarantee that it accepts 1000 strings only?
0
0
Firstly they mentioned finite automata so  if we can consider NFA, as it is said 'n' is finite ,number of states entirely depends on 'n' value, so for such NFA we require 'n+1' states to accept the 'n' a's ,similarly for DFA we require 'n+2' states including trap state.
0
0