We study the state complexity of languages nary worst-case examples for these three operations, that can be obtained as reversals of regular languages repre- however he did not present any proofs. Birget in his sented by deterministic ¯nite automata. We show that the works [1, 2] examined intersection and union of several ssttaattee ccoommpplleexxiittyy nof itshbeertweveeernsalolgofnaanredgu2lna.r Wlaeng¯urasgtepwroivthe ltaenrmguinagisetsic, aanudtoamlsaotothnefoqruecsotmiopnleomf etnhtes.siTzeheofsnysotnedme-that the upper bound is tight in the ternary case. Then we atic study of the state complexity of operations on rperveesersnatl.biWnaeryallsaongoubatagiens rseoamcheinogthtehrispaurptpiaelr rbeosuunltds oinn tthhee regular languages began in the paper by Yu, Zhuang, binary case. and Salomaa [24]. This work was followed by papers studying state complexity of operations on unary languages [17] and on ¯nite languages [3], complexity of proportional removals [5], and shu²e in [4]. 1 Introduction Another stream of research is the study of so called \magic" numbers, where not only worst-case complexRegular languages and ¯nite automata are the old- ities are important, but also all values that can be est and the simplest topics in computer science. They obtained as a corresponding complexity are considhave been investigated since the 1950s. Despite their ered. The problem was stated by Japanese authors simplicity, some problems are still open. Probably the Iwama, Kambayashi, and Takaki [9] who asked what most challenging is the question of how many states values can be obtained as the size of the minimal deare su±cient and necessary for two-way deterministic terministic automaton equivalent to a given n-state automata to simulate two-way nondeterministic au- nondeterministic automaton. The values that cannot tomata which is connected to the well-known be obtained in such a way are called \magic" numbers DLOGSPACE vs. NLOGSPACE problem. in [10]. The following research showed that there are Motivating by applications of regular languages in no magic numbers in the ternary case [12], while a lot software engineering, programming languages, and of them exist in the unary case [6]. The binary case is other areas in computer science, as well as by their im- still open. portance in theory, this class of languages is intensively Similar results for the size of nondeterministic austudied in recent years; for the discussion, we refer the tomata for complements can be found in [19], for the reader to [8, 23]. Various areas in this ¯eld are now union and intersection in [7], and for the reversal and deeply and intensively examined. One of such areas star in [11]. In all cases, the whole range of complexiis descriptional complexity which studies the cost of ties can be obtained, however while in the case of union description of languages represented by di®erent for- and intersection the used alphabet is ¯xed, in the case mal systems such as deterministic and nondetermin- of reversal and star, the alphabet grows exponentially istic ¯nite automata, two-way automata, regular ex- with n. pressions, or grammars. In this paper, we continue the study of the state Rabin and Scott in 1959 [18] described an algo- complexity of reversals of regular languages. In 1966, rithm for the conversion of nondeterministic ¯nite au- Mirkin [14] pointed out that Lupanov's ternary worsttomata into deterministic automata known as the sub- case example is a reversal of a deterministic automaset construction. The algorithm shows that every ton, which proves that the complexity of the revern-state nondeterministic automaton can be simulating sal of a language accepted by a ternary n-state deterby at most 2n state deterministic automaton. In 1963, ministic automaton is 2n. The binary language with Lupanov [16] proved the optimality of this construc- more than one accepting state reaching this upper tion by describing a ternary and even a binary regular bound has been given in 1983 by Leiss [15]. In 2004, language accepted by an n-state nondeterministic au- the paper [20] claimed a binary worst-case example tomaton that requires exactly 2n deterministic states. with a single accepting state. Unfortunately, the reMaslov in 1970 [13] considered the state complex- sult does not hold: in the case of n = 8, the number ity of union, product, and Kleene star. He gave bi- of reachable states in the subset automaton for the re-
versal is 252 instead of 256. Since the result has been Two automata are equivalent if they recognize the used in the literature several times, our ¯rst aim is same language. A dfa (an nfa) M is called minimal if to present a correct example, and a correct proof. We every dfa (every nfa, respectively) that is equivalent to start with an observation that all states in the subset M has at least as many states as M . It is well-known automaton corresponding to the nfa that is obtained that a dfa M = (Q; §; ±; s; F ) is minimal if all its as a reversal of a minimal dfa are pairwise inequiva- states are reachable from the starting state and no two lent. We show that the state complexity of the rever- its di®erent states are equivalent (states p and q are sal of an n-state dfa language is between log n and 2n, equivalent if for all strings w in §¤, the state ±(p; w) is and present a ternary worst-case example with a very accepting if and only if the state ±(q; w) is accepting). simple proof of reachability of all subsets. In a much Every regular language has a unique minimal dfa, up more di±cult way, we prove that the upper bound 2n to the naming of states. However, the same result does is tight also in the binary case. Our witness automaton not hold for nfa's. has a single accepting state, and is uniformly de¯ned The state complexity of a regular language is the for all integers n. Therefore, it can be used in all cases number of states in its minimal dfa. A regular lanwhere the incorrect result from [20] was used. We next guage with deterministic state complexity n is called ¯nd binary n-state deterministic automata that need an n-state dfa language. n + 1 or n + 2 deterministic states for their reversals. Every nfa M = (Q; §; ±; S; F ) can be transformed Finally, we present binary 1-, 2-, and 3-state automata to an equivalent deterministic ¯nite automaton M 0 = that reach all particular values from log n to 2n as the (2Q; §; ±0; s0; F 0) thanks to an algorithm known as the state complexity of their reversals. \subset construction" in the following way. Every state of the dfa M 0 is a subset of the state set Q. The starting state of the dfa M 0 is the set S. The transition 2 Preliminaries function ±0 is de¯ned by ±0(R; a) = Sr2R ±(r; a) for every state R in 2Q and every symbol a in §: A state R This section gives some basic de¯nitions, notations, in 2Q is an accepting state of the dfa M 0 if it conand preliminary results used throughout the paper. tains at least one accepting state of the nfa M: We For further details, we refer to [21, 22]. call the dfa M 0 the subset automaton corresponding
Let § be a ¯nite alphabet and §¤ the set of all to the nfa M . The subset automaton M 0 need not strings over the alphabet § including the empty be minimal since some states may be unreachable or string ". The length of a string w is denoted by jwj. equivalent.
A language is any subset of §¤. We denote the cardi- We next give the de¯nitions and some preliminary nality of a ¯nite set A by jAj and its power-set by 2A. results concerning the reversal operation. M =A d(Qet;e§rm; ±in;sis;tFic),¯wnihteeraeuQto misaaton¯n(idtefas)eits oaf 5s-ttautpelse, De¯nition 1. The reversal wR of a string w is de§ is a ¯nite input alphabet, ± is the transition function ¯ned as follows: "R = " and if w = a1a1 ¢ ¢ ¢ an with taphnaadpteFrm, aaispllstdhQfea£'sse§taroetfoaaQscsc;uesmptieisdntghtoestsbatteaersct,oinmFgpµsletatQet,e.,tIhsna2tthQisis,, aaila2Tngh§uea,grteehveLenrsiwaslRthoef=laaanndgafuana¡gA1e ¢L¢=¢Ra(=2Qa1f;.w§TR;±hj;esw;rFe2v)eLrigssa.lthoef the next state ±(q; a) is de¯ned for every state q in Q nfa AR obtained from A by reversing all transitions and every symbol a in §: The transition function ± is and by swapping the role of starting and acceptgeneralized to a function from Q£§¤ to Q in a natural ing states, that is AR = ¡Q; §; ±R; F; fsg¢, where way. A string w in §¤ is accepted by the dfa M if the ±R (q; a) = fp 2 Q : ± (p; a) = qg. state ±(s; w) is an accepting state of the dfa M . The Proposition 1. The reversal of a dfa A recognizes language accepted by the dfa M , is the set L(M ) = the language L (A)R. fw 2 §¤ j ±(s; w) 2 F g.
A nondeterministic ¯nite automaton (nfa) is Proof. We prove that a string w is in L (A)R if and a 5-tuple M = (Q; §; ±; S; F ), where Q; §; S and F are only if the string w is accepted by the nfa AR. de¯ned identically as for a dfa, S is the set of starting states, and ± is now the nondeterministic transition function that maps Q £ § to 2Q. The transition function can be naturally generalized to the domain Q £ §¤. A string w in §¤ is accepted by the nfa M if the set ±(q0; w) contains an accepting state of the nfa M: The language accepted by the nfa M is L(M ) = fw 2 §¤ j ±(S; w) \ F 6= ;g: Fig. 1. The string wR is accepted by the dfa A. in the subset automaton corresponding to the nfa M .
Then, without loss of generality,there exists a state q in Q such that q 2 S and q 2= T . It follows that the string wq is accepted by the subset automaton from state S but not from state T . Thus the states S and T Theorem 2. All states in the subset automaton corresponding to the reversal of a minimal dfa are pairwise inequivalent.
Proof. Let us show that every nfa obtained as the reversal of a minimal dfa satis¯es the condition in Lemma 1. Let q be a state of the nfa. Since state q is reachable in the given dfa, there exists a string x such that the starting state of the dfa goes to state q by x, as illustrated in Fig. 3.
the starting state s goes to an accepting state f in F by wR. It follows that the starting state f of the nfa AR goes to the accepting state s of AR by w, and so w is accepted by AR.
Next, if a string w is accepted by the nfa AR, then there is a starting state f in F that goes to the accepting state s of AR by w. It turns out, that in the dfa A, the starting state s goes to an accepting state f by wR. Thus the string wR is in the language L (A), and so the string w is in the language LR (A).
Corollary 1. The reversal of every regular language is a regular language.
Theorem 1. Let L be a regular language accepted by a minimal n-state dfa. Then the minimal dfa for the language LR has at most 2n and at least dlog2ne states.
Proof. Let A be an n-state dfa for a language L. The is a contradiction since in the dfa we woud have two reversal AR of the dfa A is an n-state nfa for the language LR. After applying the subset construction to this nfa AR, we get at most 2n-state dfa for the landi®erent computations on the string x. Hence the nfa satis¯es the condition of Lemma 1, and so all states in the corresponding subset automaton are pairwise guage LR. Now since (LR)R = L, the lower bound inquivalent. is dlog ne. tu tu
We now prove quite interesting result that in the subset automaton corresponding to the
reversal of a minimal dfa, all states are pairwise inequivalent.
This means that we need not prove inequivalence of states troughtout the paper.
Lemma 1. Let for each state q of an nfa there exists a string wq such that wq is accepted by the nfa from state q, but is not accepted from any other state. Then 3
We start with the upper bound 2n in the ternary case.
The next theorem presents a ternary worst-case example for the reversal with a very simple proof of reachability of all subsets.
Theorem 3. For every integer n with n ¸ 3, there exists an n-state dfa A over a three-letter alphabet in the corresponding subset automaton, all states are such that the minimal dfa for the reversal of the lanpairwise inequivalent. guage L(A) has 2n states.
Proof. Let M = (Q; §; ±; S; F ) be an nfa, and let for Proof. Let A be the minimal n-state dfa shown in each state q in Q, wq be a string that is accepted by M Fig. 4. Construct an nfa for the reversal of the lanonly from state q. Let S and T be two di®erent subsets guage L(A) from the dfa A by reversing all transitions, tu tu
Fig. 3. State q is reachable in the dfa A (left); p 6= q in the nfa AR (right) implies two distinct conputations of the dfa on the string x.
This means that the string xR is accepted by the nfa from state q, see Fig. 3. We now prove that the string xR is not accepted by the nfa from any other state. Assume for contradiction that the string xR is accepted by the nfa from a state p with p 6= q. It turns out that the starting state of the dfa might go by the string x to state q as well as to state p, which
Let us show that the corresponding subset automa- symbol a, and to itself by symbol b. State 3 goes to bc 0 ab 1 ac b 2 ac
ac c a b n-1 ton has 2n reachable and pairwise inequivalent states.
We ¯rst show that every set containing state 0 is reachable. The proof is by induction on the size of sets. The basis, jSj = 1, holds true because state 0 is the starting state of the subset automaton. Assume that every set of size k, 1 · k · n ¡ 1, containing state 0 is reachable. Let S = f0; i1; i2; :::; ikg with 1 · i
1 < i2 < ¢ ¢ ¢ < ik · n ¡ 1 be a set of size k + 1. Consider the set S0 = f0; i2 ¡ i1 + 1; :::; ik ¡ i1 + 1g. The set S0 is of size k tion hypothesis. The set S0 goes to the set S by bci1¡1 since S0 goes to f0; 1; i2 ¡ i1 + 1; : : : ; ik ¡ i1 + 1 and then to S by ci1¡1. It turns out that the set S is
g by b, reachable. that the minimal dfa for the reversal of the language L(A) has 2n states.
Proof. Let us consider a binary n-state dfa A in Fig. 6 with states 0; 1; : : : ; n ¡ 1, where n ¸ 4, state n is the starting state and state 0 is the sole accepting state.
For all i = 4; 5 : : : ; n ¡ 1, state i goes to state i ¡ 1 by state n ¡ 1 by symbol a, and to state 2 by b. State 2 goes to state 1 by a, and to state 3 by b. State 1 goes to state 0 by both symbols a and b. State 0 goes to state 2 by a, and to itself by b. In the case of n = 2 or n = 3, there are some small changes in the structure of the automaton. If n = 2, then state 0 goes to state 1 by symbol a. If n = 3, then state 2 goes to itself by symbol b.
of the language L (A) by exchanging the starting and tu
We will consider two cases: 1. n = 3k + 1 or n = 3k + 2, 2. n = 3k, where k is a positive integer.
1. If n = 3k + 1 or n = 3k + 2, then the number of states in the second
part is 3 (k ¡ 1) + 1 or 3 (k ¡ 1)+2. Thus these two numbers are are relativily prime. First, the set f0; 1g is reached from the starting set f0g by symbol b. Now we demonstrate how to add a new state ` to a set f0; 1g [ S, where S is a subset of the second part with ` 2= S, to get a set f0; 1g[S [ f`g. By symbol a, we can rotate states in both parts. and contains state 0, and so is reachable by the induc- the determinisation of the reversal, we get a four-state
We next prove the reachability of sets with- accepting states, and by reversing all transitions in the out state 0. Let S = fi1; i2; :::; ikg with 1 · i ¢ ¢ ¢ < ik · n ¡ 1. Then the set S is reached from the set f0; i2 ¡ i1; : : : ; ik ¡ i1g, containing state 0, by ai1 .
1 < i2 < dfa A, see Fig. 7. We are going to show that the corresponding subset automaton has 2n reachable states.
To make the proof more understandable, we call the lows from Theorem 2.
This completes the proof since the inequivalence folFinally, the empty set is reached from the set f1g by b. set of states f0; 1; 2g the ¯rst part, and the set of states f3; 4; : : : ; n ¡ 1 g the second second part of the nfa. 4
Binary alphabet and upper bound dfa and claim that its reversal requires 2n deterministic states. Unfortunately, the example does not work: in the case of n = 8, the resulting dfa has 252 reachable states instead of 256. The next theorem describes correct binary n-state witness dfa's with a single accepting state, uniformly de¯ned for every n with n ¸ 2.
The authors of the paper [20] present a binary n-state of states in the ¯rst part is three, while the number the string ax. Apply the string ax to the set f0; 1g [ S, and then apply symbol b. We get the set f0; 1; 3g [ S0, set to f0; 1; 2g. When ¯nally setting the ¯rst triple, we also show how to set it with an arbitrary con¯guration Consider the set f0; 1; `g. Since the sizes of the two parts are relatively primes, there exists an integer x denote the states of this triple by `0; `1; `2. We choose which con¯garation for this triple we want obtain, and such that the set f0; 1; `g goes to the set f0; 2; 3g by show that we set this con¯guration with the 0-th triple where S0 is a rotation of the set S by the string ax. in the 0-th triple. So, ¯rst let ` ¸ 2. A con¯guration And now, again, there exists an integer y such that the set f0; 1; 3g [ S0 goes to the set f0; 1g [ S [ f`g by ay.
So, in this way, we can reach every set f0; 1g [ S. Let in this triple is given by a subset S of f3; 4; 5g. We ¯rst count the numbers of a's in the string on a path from f0; 1; 2g to f0; 1; 2g [ S in the dfa B, and denote us show how to get every subset of states in ¯rst part it by a#. Now consider some starting strings: without changing the second part. Every set f0; 1g [ S goes to the set f1; 2g [ S as well as to the set f0; 2g [ S by an appropriate numbers of a's. Every set f1; 2g [ S goes to the set f2g [ S by bb, and then to f0g [ S and f1g [ S by an appropriate numbers of a's. Every set f0; 2g [ S goes to the set f0; 1; 2g [ S by bb. Finally, completes the proof of reachability if n = 3k + 1 or every set f1g [ S goes to the set ; [ S by bb. This triple by one the of starting strings as0 ; as1 ; as2 : if as0 = a3:(k¡1¡`+1), as1 = a3:(k¡1¡`+1)¡1, as2 = a3:(k¡1¡`+1)¡2; di®erent starting strings are needed because the number of a's must be a multiply of 3 in the end.
Next we move the `-th triple to the place of ¯rst a# (mod 3) = 0 we use as0 so we get `0; `1; `2 at the place of the ¯rst triple, if a# (mod 3) = 1 we use as1 so we get `1; `2; X at place of ¯rst triple, if a# (mod 3) = 2 we use as2 so we get `2; X; X at place of ¯rst triple where X is a state from some other triple, n = 3k + 2.
2. If n = 3k, we can split the states of the nfa into triples, the ¯rst part is a triple 0, and the second part consists of triples 1; 2; : : : ; k ¡ 1. We ¯rst reach baabb. Let us show how to set a triple in the second part without changing the other triples. We use the automaton B shown in Fig. 8. In automaton B, every set is reachable from the set f0; 1; 2g. Assume we want the set f0; 1; 2g from the starting set f0g by the string thus we cannot modify X. to set the `-th triple with 2 · ` · k ¡ 1, and let us the other triples. Similarly, if the starting string was up corner), and dfa for L(A)R, the main part of the picture.
Red lines correspond to the transitions by symbol b, and blue lines to the transitions by symbol a.
Next we proceed by the string w and count the number of a's. If the starting string was as0 , after the 1st, 4th, 7th, . . . symbol a, we apply a rotation arot where a arot = a3:(k¡2), so that we do not modify as1 , we apply the rotation arot after the 2nd, 5th, 8th, . . . symbol a. Finally, if the starting string was as2 , we apply the rotation after the 3rd, 6th, 9th, . . . symbol a.
move the triple to its place `: we just need to apply the string a3(`¡1) (a back string).
So the complete string consists of one of the strating strings, a new route string, and a back string. Thus in this way, we can set the 0-th triple f0; 1; 2g with all triples except for the ¯rst triple. We set the ¯rst triple in a similar way, but now we use paths from f0; 1; 2g to every state in the dfa B. That means that all subsets are reachable. This completes the proof of reachability for n = 3k. 5
tu We now show that we cannot reduce the size of the alphabet to one symbol.
Theorem 5. The minimal dfa for the reversal of every unary n-state dfa language has n states. Proof. Every string w in a unary language L consists only of symbols, for example, a. Therefore, w = wR, and so L = LR. That means that the reversal of the language L has also complexity n.
In this section, we examine the reversals of regular languages that can be accepted by one-, two- and threestate dfa's. We ¯rst observe that the reversal of a onestate dfa language is the same language. It turns out that that the reversal of no two-state dfa language can be accepted by a one-state dfa, and so in this case, the lower bound log 2 cannot be reached. On the other hand, we show that all other possible values, that is, 2, 3, and 4, can be obtained as the size of the minimal dfa for the reversal of a two-state binary dfa language. We next prove that all values from 2 to 8 can be reached as the number of states in the minimal dfa recognizing the reversal of a binary language represented by a three-state deterministic ¯nite automaton. Theorem 6. The reversal of every one-state dfa language is a one-state dfa language.
Proof. Let us prove the theorem by inspecting all onestate automata. We only have two possibilities shown in Fig. 9. If the state is accepting, then the automaTheorem 8. For each ® with 2 · ® · 8, there exists a three-state binary dfa A such that the minimal dfa for the reversal of the language L(A) has exactly ® states.
Proof. Similarly as in the previous proof, we show the appropriate three-state binary automata for ® = 2; 3; 4; 5; 6; 7; 8 in Figures 13, 14, 15, 16, 17. Fig. 10. The dfa A (top left), the reversal of A (bottom left), the subset automaton for the reversal; ® = 2. Fig. 11. The dfa A, the reversal of A, the subset automaton for the reversal; ® = 3. 7
In this section, we describe n-state dfa's whose reversals need exactly n + 1 and n + 2 deterministic states. Notice that by Theorem 5, the reversal of an n-state unary language needs exactly n-states.
Theorem 9. For every integer n with n ¸ 2, there exists an n-state dfa A over a two-letter alphabet such that the minimal dfa for the reversal of the language L(A) has n + 1 states.
Proof. Let n ¸ 2. Consider the n-state dfa A shown in Fig. 18 with states 1; 2; : : : ; n, of which 1 is the starting state and also the sole accepting state. For all i = 1; 2; : : : ; n ¡ 1 state i goes by symbol a to state i + 1, and state n goes by symbol a to itself. For all and state 1 goes by b to itself. The dfa A is minimal since for two states i; j with i < i, the string bi¡1 is accepted from state i but not from state j.
guage L (A) by swapping the starting and accepting states, and by reversing all transitions in A. Let us show that the corresponding subset automaton has n + 1 reachable states . The set f1g is reachable because it is the starting state in the subset automaton.
The set f1g goes to the empty set by symbol a, and to the set f1; 2g by symbol b. Every set f1; 2; : : : ; ig with 2 · i · n ¡ 1 goes to the set f1; 2; : : : ; i ¡ 1g by a, and to the set f1; 2; : : : ; i + 1
g by b. The set f1; 2; : : : ; ng goes to itself by a and b. Thus the sets f g
1 , f1; 2g, : : :, f1; 2; : : : ; ng, and the empty set are reachable, while no other set is reachable. It follows that the minimal dfa for the reversal of L(A) has n + 1 sets. Theorem 7. For each ® with 2 · ® · 4, there exists i = 2; 3; : : : ; n state i goes by symbol b to state i ¡ 1, left), the subset automaton for the reversal; ® = 2. g by symbol a, and the set fng
Theorem 10. For every integer n with n ¸ 2, there exists an n-state dfa A over a two-letter alphabet such that the minimal dfa for the reversal of the language L(A) has n + 2 states.
Construct an nfa for the reversal of the language L (A) by swapping the starting and accepting states, and by reversing all transitions in A. Let us n + 2 reachable states. The set f1g is the starting state in the suset automaton. For all i = 1; 2; : : : ; n ¡ 1, the able, while no other set is reachable. goes to the set f1g by symbol a. The set f1g goes to set f1; 2; : : : ; ng by symbol b. Each set fig with i ¸ 2 goes to the empty set by symbol b. The set f1; 2; : : : ; ng goes to itself by symbols a and b. So the sets f g
1 , f2g, : : :, fng, f1; 2; : : : ; ng, and the empty set are reach
tu 8
We studied the state complexity of languages that can be obtained as reversals of regular languages represented by deterministic ¯nite automata. We showed that the state complexity of the reversal of a regular language with state complexity n is between log n and 2n. We gave a simple proof of a fact that the upper bound is tight in the ternary case. Then we presented binary languages reaching this upper bound on the reversal. Our witness deterministic automata have 14. B.G. Mirkin: On dual automata. Kibernetika (Kiev) 2, a single accepting state, which can be used in some 1966, 7{10, (in Russian). English translation: Cyberresults in the literature instead of an incorrect exam- netics 2, 1966, 6{9. ple in [20]. We also obtained some other partial results 15. E. Leiss: Succinct representation of regular languages in the binary case for one-, two-, and three-state au- by Boolean automata. Theoret. Comput. Sci. 13, 1981, tomata. We described automata, the reversal of which 323{330. 16. U.I. Lupanov: A comparison of two types of ¯nite auhas state complexity n, n + 1, and n + 2. In future, tomata. Problemy Kibernetiki 9, 1963, 321{326. we want to do statistics of reachable complexities for 17. G. Pighizzini, J. Shallit: Unary language operations, the reversal of all automata up to ¯ve states. We also state complexity and Jacobsthal's function. Internat. want to ¯nd automata, with other complexities then J. Found. Comput. Sci. 13, 2002, 145{159. n, n + 1, n + 2, and 2n, and try to answer the question 18. M. Rabin, D. Scott: Finite automata and their deciwhether all values from log n to 2n can be reached, sion problems. IBM Res. Develop. 3, 1959, 114{129. or whether there are some \magic numbers" for the 19. A. Szabari: Regular languages and descriptional comreversal. plexity. PhD. Thesis, in preparation. 20. A. Salomaa, D. Wood, S. Yu: On the state complexity of reversals of regular languages. Theoret. Comput.
References Sci. 320, 2004, 315{329. 21. M. Sipser: Introduction to the theory of computation.
PWS Publishing Company, Boston, 1997. 22. S. Yu: Chapter 2: Regular languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages - Vol. I, Springer, Heidelberg, 1997, 41{110. 23. S. Yu: A renaissance of automata theory? Bull. Eur.
Assoc. Theor. Comput. Sci. 72, 2000, 270{272. 24. S. Yu, Q. Zhuang, K. Salomaa: The state complexity of some basic operations on regular languages. Theoret.
Comput. Sci. 125, 1994, 315{328.