CODEWITHSUNDEEP
automatafinite-automata
ankit
ankit

Reputation: 347

DFA for a set {1,2,4,8,..,2^n} written in binary

I have to construct a minimal Deterministic Finite State Automaton(DFA) for a set :-

L = {1,2,22,23,24....,2n} where numbers 1,2,22,23,24....,2n written in binary and Input alphabet = {0,1} and 'n' is a non-negative integer.

I have constructed a minimal DFA as :-

enter image description here

Regular Expression(RegEx) for this DFA should be :- 10* because Language contains strings {1,10,100,1000,....}

Now, I am confused whether should I have to consider a unique representation for every string of the given set(Language) or not.
Here , string '1' has infinitely many representations like {1,01,001,0001,.....} Similarly, I can get many representations for every string of the set by appending zeros initially.
So, If I consider it then I am getting RegEx as 0*10*.
According to this RegEx, my equivalent minimal DFA will be :-
enter image description here

So, My question is : which DFA is correct according to the given description of the set which I have written initially. Should I have to mention that all strings should be started with '1' or every string has unique representation for the precise description of the language so that I can get the unique minimal DFA for the given set.
Please help!

Upvotes: 1

Views: 1981

Answers (1)

Dusan Radovanovic
Dusan Radovanovic

Reputation: 1679

I would use the second one because it is more flexible and if you have a situation where you need to store your number in a memory where memory field is bigger than your number(number of bits), you would need to add initial zeros to store it.

Upvotes: 1

Related Questions