In this work we study some aspects of state-complexity related to the very famous Sakoda-Sipser problem. We study the state-complexity of the regular operations, we survey the known facts and, by the way, we find some new and simpler proofs of some well known results. The analysis of the state of art allowed us to find a new and meaningful notion: Real-state processing. We investigate this notion, looking for a model of deterministic finite automata holding such an interesting property. We establish some preliminary results, which seem to indicate that there does not exists a model of deterministic finite automata having realstate processing of regular expressions, but, on the other hand, we are able of exhibiting a deterministic model of finite automata having real-state processing of star free regular expressions.

We study the problem of discerning strings with deterministic finite state automata (DFAs, for short). We begin with a survey on the historical and algorithmic roots of this problem. Then, we focus on the maximun number of states that are necessary to separate two strings of a given length. We survey the most important results concerning this issue and we study the problem from the point of view of some alternative models of automata. The preliminary results concerning the last issue motivate us to formulate a conjecture stating that DFAs can separate any pair of strings by using a logarithmic number of states. We give some evidence supporting our conjecture.