AP06_1.vp 1 Introduction The state of a (logical) object is generally not specified and is intuitively regarded as sufficiently obvious. Often, the state is conceived in connection with the input history of the object. The state of an entity, let us say the determination of its state alphabet, identification of the object is fatally depend- ent. Moreover, if the identification of an entity follows one and the same objective even several different final automaton models of the object, which satisfy the given objective, can be constructed [1]. The observer who identifies the object may be satisfied with the recurrent definition of the state presented in this article and, as we hope, could be persuaded that a stimulus affecting the object only initiates (provokes) the transition between the states of the object whereas it is the initial state of the transition which effectuates the transition. It is to be believed that (the physical untenability of) the so called determinization of a nondeterministic final automaton model will be shown to be physically untenable as it initially respects the randomness, which it later formally ignores. 2 State of a logical object A logical object receives and sends quantum signals. Let- ters from the input X and output Y alphabets denote individ- ual input and output quanta, respectively. By analogy, the quanta of the anticipated inner signals (states) in the object are denoted by letters of the state alphabet S. The sampling of the input signals (stimuli) is random, and is determined by the neighbourhood of the object. The sam- pling of state and output signals (responses or reactions) in an asynchronous object is derived state from the sampling of output signals. In a synchronous object the sampling is done indirectly in a tenacious way so that the subject has delegated the sampling to the generator of the synchronizing pulses. If the object synchronises itself by means of a synchroniser, the situation can be denoted as an autosynchronous object, or the object of state sampling and the respective responses ‘forces’ the neighbourhood to accept a speed independent object. Let T be a set of sampling moments and the binary rela- tion � : : ,T t t2 � be a relationship of a strong arrangement on T, t t� �, meaning that moment t was initiated before moment �t . The monomorphism from T,� to N, � is said to hold if there exists a simple function f T t v: :� N � such that t t f t f t� � � � �( ) ( ), where N is a set of integers including zero. If f t v( ) � and f t v( )� � � 1, moment t is said to have initiated immediately before moment �t . In addition, let there be AN, esp. A(�) or A�, where A is one of the alphabets and � is the time moment �� N), set {N � A}, esp.{{ }� � A}, or {� � A}of all representations N A a a a ai i� �: , , ( )0 10 1 0 1 � � � � , spec. { } : ( )� � �� �A a ai� , or � � �A a ei: ( )and . Let us therefore, denote �A N , esp . �A { }� , either AN or A� (�{e}), esp. either A{�}, or A� (�{e}) and also �a a 0 1 � , esp. �a � , either a0 a1 … or e, esp. either a� or e. The performance of a deterministic logical object with a given input X, state S, and output Y alphabets can be modeled by a system of functions consisting of the � transition function � � � � � � �: : ,{ } { } { }S X S s x s� � � �1 1� � output function � �� � � � � � �: : ,{ } { } { }S X Y s x y� � �� 1 i.e. either s x y� � �, � �1 or s y� �� of the Mealy, or Moore, type respectively, where � is the current moment of sampling and x�, s�, y� are the respective current stimulus, state, re- sponse; moment � � 1 is the immediate follower of moment � and s� � 1 is the follower state of state s� . However, since the future state s� � 1, is not yet at our disposal (!), the value of the transition function is given by the current predication of state s pred s� � �� �1 1– ( ) , i.e. � �� � � � � � � � �: : , ( ) { } S X S s x pred s� � � �1 1� . Being aware of the fact above, we will keep to the tradi- tional notation of function �. Note also that the transition function offers, in fact, two possibilities causing the transition from state s� to that of s� � 1: the starting state of transition s� and stimulus x�; it remains only to decide which cause is the dominant one. Since the postdiction post� (s��1) of predecessor states s��1 to the current state is not generally unambiguous, i.e., for � � � �� �� � � � �s x s x si j� � � �� �1 1 1 1, , we can admit s s i ji j � �� �� �1 1( ) we will introduce a general- ized transition � function � � � � � � � � �� � �: : ,{ } { , , , } { }S X S s x x x s� �� � �1 1 1� � � recurrently so that � � � � �� �� � � ( ( , ), )s x x x x s� � � . © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ 61 Czech Technical University in Prague Acta Polytechnica Vol. 46 No. 1/2006 State of a Logical Object J. Bokr, V. Jáneš The paper deals with the state and performance of a logical object on a state-differentiating level and with the so called determinization of a finite – automaton model. Keywords: logical object, state, state transition, finite automaton. It can be intuitively stated that the state of an object is defined by the entire input cumulated prehistory H of the ob- ject. The response y� is a value of the output function: � � � � � � �: : ,{ } { } { }[ ] [ ]H X Y h x y� � � of an output block O of the object, where h� is the instanta- neous input prehistory. Therefore, we expect the given object to be divided into two components: the fixator F of the input prehistory h and the output block O (Fig. 1). Fixator F records and issues the input prehistory; since, however, F does not delete (!) every recorded prehistory H, the prehistory is kept in a cumulated form (let us imagine, e.g., the whole Bible recorded on one current page of paper). A performance model of fixator F is a transition function � � � � � � �: : ,{ } { } { }H X H h x h� � � �1 1� . First let there be H X N� and H x x x x x x X N� � �0 1 1 0 1 1� �� �( ) [2] and consider an initially finite automaton model of the fixator [3] F � X X eN, , ,�1 where �1 is the transition function � � � � � � 1 0 1 1 0 1 1 : : [ ], [ ] [ ] { }X X X x x x x x x x x N N� � � � � � � � and N is a set of integer numbers including zero. For the tran- sition function �1 there holds (i j� ): � x x x x x x x x x x x x xi i i j j j i i i j j j 0 1 1 0 1 1 0 1 1 0 1 � � � � � � � �� � �� � � � ��1x � x x x x x x x x x x x x xi i i j j j i i i j j j 0 1 1 0 1 1 0 1 1 0 1 � � � � � � � �� � �� � � � ��1x � (Fig. 2a) and not x x x x x x x x x x x x xi i i j j j i i i j j j 0 1 1 0 1 1 0 1 1 0 1 � � � � � � � �� � �� � � � ��1x , (where �Ţis the statement of an implication) which can also be rightly required (Fig. 2b), � it can be legitimately required that � � � �( )x x x x x x x0 1 1 0 1 1� �� �� , esp. � �( , )e x e� , this is, how- ever, contradictory (Fig. 3). Let us write more cunningly H X N� �( / ) and h x x x x x x X N� �{ } ({ } ( / )0 1 0 1� �� � [3, 4, 5], where ( / )X N � is the finite partition on XN defined on XN through the Nerode equivalence the class of partition ( / )X N � is denoted and we can consider the fixator model F � �X X eN, ( / ), , { }�2 , where �2 is the transition function � � � � � 2 0 1 1 0 1 1 : ( / ) ( / ) : , { } [{ }] {[ X X X x x x x x x x N N� � � � � � � � � ] }x .� We have still to define the right-side congruence Nerode equivalence � on X N; the input words x x xi i i 0 1 � � and x x xj j j 0 1 � � (i j� ) are said to be right-side congruent, if there holds � � �� �2 0 1 2 0 1( ) ( ){ }, { },e x x x e x x xi i i j j j� �� � � � � � �2 0 1 1 2( ){ },e x x x x x xi i i� �� � � � � �� � � � �2 0 1 1 2( ){ },e x x x x x xj j j� � For the transition function �2 there is (i j� ): � { } { }x x x x x xi i i j j j 0 1 1 0 1 1 � � � �� �� � � �� �{ } { }x x x x x x x xi i i j j j 0 1 1 0 1 1 � � � � � � � { } { }x x x x x xi i i j j j 0 1 1 0 1 1 � � � �� �� � � � � � �{ } { }x x x x x x x xi i i j j j 0 1 1 0 1 1 � � � � � � where � � means either = or � , � { , } { }a x e� � is legitimate. If we write both S X N� , s0 � e, s� � x0 x1… x��1 and s x x x x� � �� ��1 0 1 1� and then S X N� �( / ) , s0 � {e}, s� � {x0 x1… x��1} and s x x x x� � �� ��1 0 1 1{ }� , then, obviously, the first conception is equivalent to the transition: � s s s x s xi j i j � � � � � �� �� � �1 1( , ) ( , ), but this is not so with the transitions: � s s s x s xi j i j � � � � � �� �� � �1 1( , ) ( , ) 62 © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ Acta Polytechnica Vol. 46 No. 1/2006 Czech Technical University in Prague x h y O F Fig. 1: Division of the object into fixator F and output block O a) b) Fig. 2: Pairs of legitimized transitions of fixator F: a) correct, b) contradictory Fig. 3: Justified, but contradictory transitions of fixator F � � � � �1( , )s x s� , esp. �1 0 0 0( , )s x s� , whereas, even under the condition that the second concep- tion will cope with the transitions: � s s s x s xi j i j � � � � � �� �� � �2 2( , ) ( , ) � s s s x s xi j i j � � � � � �� �� � �2 2( , ) ( , ) � � � � �2( , )s x s� , esp. �2 0 0 0( , )s x s� , it is still closely connected with the problematic acceptance of the empty word e by the object. Example 1: Let the input alphabet {a, b, c} be given, and let at: 1) S e c bc c bc b c bc ba c bc a� � � � �{ ,( ) ,( ) ,( ) ,( ) }* * * * , where *, � are respective iterations, disjunctions and concatenation of the Kleene algebra of regular expressions, a transition function �1 being defined as: � �1( , )e e e� , �1( ,( ) ) ( ) * *e c bc c bc� � � , � �1( ,( ) ) ( ) * *e c bc b c bc b� � � , � �1( ,( ) ) ( ) * *e c bc ba c bc ba� � � , �1( ,( ) ) ( ) * *e c bc a c bc a� � � . If we make an unwilling and unreal compromise that 1 � � �e c bc( )*, 2 � �( )*c bc b and 3 � � � �( ) ( )* *c bc ba c bc a, we obtain the transition diagram from Fig. 4. 2) S e c bc c bc b c bc ba c bc a� � � � � �{ }{ ,( ) },{( ) },{( ) ,( ) }* * * * � { , , }1 2 3 , where 1 � �{ ,( ) }*e c bc , 2 � �{( ) }*c bc b and 3 � � �{( ) ( ) }* *c bc a bc , the transition function �2 being defined: � � �2 21 1 1( , ) ( , ( ) ) *e c bc� � � , � �2 1 2( , ( ) ) *c bc b� � , � � �2 21 1 3( , ( ) ) ( , ( ) ) * *c bc a c bc ba� � � � , we obtain Fig. 4. Not defining the state as a cumulated input history or as a block of the final decomposition (Nerode), we can now recurrently define the state of a logical object: � the initial state s0, i.e., � ( ,|)s s0 0� , where | is a separator, is a state, � s �1 is a state if there holds � ( , , , , )s x x x0 0 1 1� � . Let us consider the transition function � � � �( , )s x s� �1 and ask whether according to the transition function the cause of the transition from initiating state s� to follower state s� � 1 can be assumed. A general opinion is that the cause of the state transition is merely the stimulus x [6]. By analogy, the only cause of the state transition can be assumed to be its initial state s�. Both strict conceptions do not seem to be very convincing, since the cause of transition of an object to the follower state s� � 1 can be regarded both as the state s�, and the stimulus x�. Let us traditionally characterize the causes s� or x� as necessary or sufficient, respectively. (Let us admit that a sufficient cause always initiates the transition of an object to s� � 1, but need not always result in attaining the object s� � 1; if the object has attained state s� � 1, then it was certainly due to the necessary cause.) Since both � �� � � � �( , ) ( , )s x s x si j� � �1 and � �� � � � �( , ) ( , )s x s x si j� � �1 can be admitted for s si j � �� or x xi j � �� , respectively, a decision cannot be made which of the causes, s� or x�, is necessary and which is sufficient. Thus, let us characterize causes s� and x� as executing and initiating causes and decide which of them is the executing cause, and which is the initiating cause. Let us, therefore, assume the fol- lowing logical objects: a) a frog sitting on a water lily leaf in a pond, b) loose material in a discharging hopper and a truck, c) a logical object. ad a) A frog sitting on a water lily leaf – initial transition state (s�) – spots an insect – stimulus x� – jumps on to another leaf to catch the insect – follower state (s� � 1). The stimulus is obvi- ously a mere initiator of the jump, whereas the initiating state is its executor of the jump. ad b) Opening the discharging valve – stimulus x� – produces the pouring of sand from the hopper – initiating transition state s� – into the truck – follower state (s � � 1). Again, the stim- ulus only initiates the pouring of sand, whereas the sand in the discharging hopper is the executor of the pouring. ad c) Since dynamic logical objects are designed through ca- nonical decomposition and since a substitute of the given object is usually a parallel register of flip flop circuits or unit delay circuits, and since each flip flop circuit is again designed through canonical decomposition (without respect to the in- tuitively designed RS-flip flop circuit), and since the substitute of the selected flip flop circuit in canonical decomposition is a unit delay circuit, let us examine its action. The unit delay circuit is the only dynamic element, since its finite – automa- ton model is an ordered trio �, ,Q D� where �, Q is the respective input state alphabet and � is the transition function � � � � � � �D Q D pred q: ( ) : ( ) { } { } { } � � �� �1 1 proving the indivisibility of the unit delay circuit. Across the pulse front, or the fall time of stimulus D�, when identifying the imperceptible intermediate state with the initial state of transition q� (otherwise a delay cannot be mentioned), the delay circuit, after the given time has elapsed, passes from initial state q� to follower state q� � 1 immediately and spontaneously. Spontaneous realization of delay circuit state transitions after some time has elapsed from the instant of acceptance of the change of stimulus D� by the delay circuit is, however, a © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ 63 Czech Technical University in Prague Acta Polytechnica Vol. 46 No. 1/2006 a b c 21 3 a c Fig. 4: Transition diagram of the automaton from Example 1 fiction. In which way, then, should the realization of the state transition from q� to q� � 1 through an uninvited change of stimulus D� be explained; We have to the transition from q� to q� � 1 of the respective delay circuits was usually effected by the initial state of the transition q�. Let us then follow the succes- sive action, without loss of generality, of a binary symmetrical delay circuit with the delay � according to Fig. 5 a), b). It is necessary to explain what happens to the object dur- ing the transition from state s� to state s� � 1. Without any doubt the object is in some uninteresting, imperceptible intermedi- ate state, which is not taken into account by the model. Since an object is determined by its model there is no other way than to identify the intermediate state either with initiating state s� or with follower state s� � 1 of the transition; the inter- mediate state is, in fact, made respected by the model. Since the above mentioned identification appears not to be effected it is sometimes stated that the Mealy automaton produces a response y� during the transition � � � �( , )s x s� �1. If the inter- mediate state of the state transition is identified either with the initiating state or with the state of the end transition, the state transition of the finite – automaton model is instanta- neous. In this way, space of a state transition in a logical object itself can be taken into account. Let us mention the acceptance of an empty word e by an object. Since the empty word e (as an empty set �) is an empty concept, i.e., a concept with a controversial content and an empty extent (an empty word does not contain any word of length 1, whereas a word is determined by the sequence of its words of length 1) the acceptance of e by a logical object can be only virtual. We say that an object with the same initial and end state s0 accepts an empty word e s e s� �� ( , )0 0 – (Fig. 6); if the reader does not agree with the above statement, we will introduce an unempty word x� on the object, which will be transferred by the object to a stable, for x� retaining state z s x z� � ��� �( , )0 , � � � �( , )z x z� , and we will state that prior to the introduction of the word x� the object accepted empty word e. Thus, the transitions � � �( , )s e s� are imaginary since the acceptance of e by the object is virtual. Only � � � �( ,| )s s� is offered, which is a virtual state transition initiated by sepa- rating word |�, where | is the separator (usually a space) and is a letter, though unpublished, of the input alphabet X. 3 ‘Determinization’ of a nondeterministic automaton Let, without generality loss, a final-automaton model of a nondetermistic logical object be a semiautomaton A A S� X, , � where � is the transition relation � � � � � � �: : , ,{ } { } { }S X S s x s� � � �1 1 and s� � 1 is one of the possible states of the followers of initial transition state s�, i.e., s S� �� � 1 1, � �S proj s x s s � � � � � � �� � 1 3 1 1 , , . The transition from state s� to just one of the possi- ble states of the followers from S��1 along with stimulus x� initiated by an implicit (inaccessible for the observer – immea- surable) random fault; the fault is not meant only as a failure of the object but also as an action effect of the neighborhood or of the object itself. The so called determinization of a nondeterministic automaton transforms a nondeterministic automaton to a deterministic one [7]. To all possible followers of each initial state of the transition of the given nondeterministic automaton we will find all of their possible followers, and then, purely in a speculative way, we will specify them as the initial states of transitions and also find of their possible followers, etc., as long as the procedure renders the sets of possible follower states that have not occurred so far. Then we will substitute each set of possible states S, formed in this way, by the only certain state of the ‘determinizated’ nondeterministic autom- aton so that the mutually different sets are assigned different states. Hence the transition function �d of the ‘determin- izated’ nondeterministic automaton: 64 © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ Acta Polytechnica Vol. 46 No. 1/2006 Czech Technical University in Prague D q �a) t b) � D T � t q 0 1 2 3 4 c) D � q � q �+1 0 1 1 11 0 0 0 Fig. 5: a) Graphical symbol, b) action, c) delay circuit transition table s 0 z � x � x � Fig. 6: Virtual acceptance of an empty word � � �� � � � d S SX S x S: : , { } { }{ }2 2 1 1� � � � � where 2S is the potency of the state alphabet S. Example 2: Construct a deterministic automaton (Table 1 b)) to a given nondeterministic automaton (Table 1 a)). After a state assignment (two left columns in Table 1 b)) we obtain a transition table of the ‘determinizated’ nondeterministic automaton (Table 1 c)). Note a formal peculiarity of determinization: the states of an immediately constructed deterministic automaton are sets of states of the given nondeterministic automaton. It is aston- ishing how the mere replacement of the sets of possible fol- lower states by a certain follower eliminates a random an ac- tion of implicit (immeasurable) faults. This peculiarity can be explained by stating that either the possible followers or the substituting certain follower are not simply states, otherwise the nondeterminism of an object is a fiction. If we were succeeded in identifying the faults, only one physically acceptable adequate nondeterministic automaton with a so called fault input could be constructed to the given nondeterministic automaton. Thus, if Z is a fault alphabet (the alphabet of explicit measurable faults), then for the tran- sition function �e of a semiautomaton X Z S e� , , � with a fault input, there holds � � � � � � � � �� e S X Z S s x z s: : , , { } { } { } { }� � � �1 � Example 3: Assume that a fault alphabet {z1, z2, z3} of the au- tomaton from Example 2 is given such that, e.g., the Table 2 holds. 4 Conclusions As a satisfactory definition of the state of a logical ob- ject and its recurrent introduction can thus be regarded, the adequacy of which is proved particularly in identifica- tion of logical objects on the state distinguishing level. The ‘determinization’ of a nondeterministic finite automaton is undoubtedly a myth. References [1] Bokr, J., Jáneš, V.: Logické systémy. Vydavatelství ČVUT, Praha 1999 (in Czech). [2] Brunovský, P., Černý, J.: Základy matematickej teórie systé- mov. Veda, Bratislava 1980 (in Slovak). [3] Harrison, M. A.: Introduction to Switching and Automata Theory. Mc Graw - Hill Book Co., New York – Sydney 1965. © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ 65 Czech Technical University in Prague Acta Polytechnica Vol. 46 No. 1/2006 a) s� � 1 x� s� a b c 1 1,2 2 4 2 3 3,4 4 3 4 3 4 4 4 2 4 b) S ��1 � � x � S � a b c 1 {1} {1, 2} {2} {4} 2 {1,2} {1,2,3} {2,3,4} {4} 3 {1,2,3} {1,2,3,4} {2,3,4} {4} 4 {2,3,4} {3,4} {2,3,4} {4} 5 {1,2,3,4} {1,2,3,4} {2,3,4} {4} 6 {3,4} {4} {2,3} {4} 7 {2,3} {3,4} {3,4} {4} 8 {2} {3} {3,4} {4} 9 {3} {4} {3} {4} 10 {4} {4} {4} {4} c) � � � 1 x� � � a b c 1 2 8 10 2 3 4 10 3 5 4 10 4 6 4 10 5 5 4 10 6 10 7 10 7 6 6 10 8 9 6 10 9 10 9 10 10 10 8 10 Table 1: Transition table of the a) nondeterministic automaton, b), c) deterministic automaton from Example 2 s��1 x�z� s� a z1 a z z( )2 3� b z z( )1 2� b z3 c z z z( )1 2 3� � 1 1 2 2 2 4 2 3 3 3 4 4 3 4 4 3 3 4 4 4 4 2 2 4 Table 2: Transition table of the deterministic automaton of the respective nondeterministic automaton from Example 2 [4] Chytil, M.: Automaty a gramatiky. SNTL, Praha 1984 (in Czech). [5] Kalman, R. E., Falb, P. L., Arbib, M. A.: Topics in Mathe- matical System Theory. Mc Graw-Hill Book Co, New York – Sydney 1969. [6] Gluškov, V. M.: Sintez cifrovych avtomatov. GIFML, Mosk- va 1962 (in Russian). [7] Hopcroft, J. E., Ullman, J. D.: Formal Languages and their Relation to Automata. Slovak translation: Alfa, Bratislava 1978. Doc. Ing. Josef Bokr, CSc. e-mail: bokr@kiv.zcu.cz Department of Informatics and Computer Sciences University of West Bohemia in Pilsen Faculty of Applied Sciences Universitní 22 306 14 Pilsen, Czech Republic Doc. Ing. Vlastimil Jáneš, CSc. e–mail: janes@fd.cvut.cz Department of Control and Telematics Czech Technical University in Prague Faculty of Transportation Sciences Konviktská 20 110 00 Prague 1, Czech Republic 66 © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ Acta Polytechnica Vol. 46 No. 1/2006 Czech Technical University in Prague