1,545 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?

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 votes
–1 votes
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'.

Related questions

7 votes
7 votes
2 answers
2
debanjan sarkar asked Sep 30, 2016
4,377 views
Number of states in minimal finite automata that accepts all binary strings that starts with 101 and is divisible by 100.A. 102B. 103C. 104D. 105
4 votes
4 votes
3 answers
3
Vikrant Singh asked Jan 25, 2015
3,158 views
What is the number of states in the minimal DFA with input symbols {0,1,2} where 2nd last symbol is 1?A. 8B. 9C. 6D. None
2 votes
2 votes
2 answers
4
Anurag_s asked Aug 15, 2015
3,224 views
Let Σ= {a}, assume language, L= { a^(2012.K) / K 0}, what is minimum number of states needed in a DFA to recognize L