Mathematica Pannonica 7

Mathematica Pannonica 7

/2 (1996), 215 { 222

1 { REGULAR LANGUAGES

DEFINED BY A LIMIT OPERATOR

Karel

Mikulasek

Department of Mathematics, Technical University, 61669 Brno, Technicka 2, Czech Republic

Received: May 1995 MSC 1991: 68 Q 45

Keywords: ¹-regular language,¹-acceptor, transition graph, limit operator.

Abstract: Finite deterministic ¹-acceptor accepting both nite and innite words over a nite alphabet is introduced. It is shown that ¹-regular lan- guages can be dened as sets of¹-words accepted by an¹-acceptor. A limit operator on regular languages is used to dene a special class of ¹-regular languages. In ¹-acceptors accepting these languages incidence relations be- tween the sets used for acceptance are determined.

1. Introduction

The paper deals with special classes of ¹-regular languages. If a nite alphabet is given, then by an ¹-regular language over we understand the union of a regular and an ^!-regular language over . In this paper we show that it is possible to dene such languages by means of a single nite-state device. A deterministic machine capable of constructing both nite and innite sequences is rst introduced in 7]. In 4] the structure of the sets constructed in 7] is investigated and in 5] a non-deterministic version of such machines is shown. An- other generalization can be found in 3] where the notion of a ^k-machine is introduced. In 6] generalized non-deterministic acceptors accepting sequences of both nite and innite length are introduced. Limit op- erators on regular languages are usefull tools for investigating relations

between regular and ^!-regular languages. In 8] and 9] they are also used for studying topological properties of ^!-languages. The operator lim used in this paper appears e.g. in 1], 2], 6] and 9]. A general- ization of some of the results of 6] gives rise to a question of how the structure of ¹-regular languages dened by inclusions between a limit closure of their words and their ^!-words is reected in the incidence of sets used for accepting words and ^!-words.

2. Preliminaries

In this paper, all the numbers are non-negative integers if not specied otherwise. By ^! we denote the least innite ordinal number.

A non-empty nite set is calledalphabet and its elementsletters. denotes the set of all nite sequences of . The empty word is denoted by . Its elements are called words. For a ^{u 2} , we write ^u =

u 1

u 2

:::un. For two non-empty words^u=^u1u2:::um,^v=^v1v2:::vk, we dene their catenation ^u:v =^u1u2:::um^v1v2:::vk. We put: ^:u=

= ^u: = ^u, ^{u 2} . The catenation of ^k identical words ^{w 2} is denoted by ^wk.

^! denotes the set of all innite sequences over . If ^{w 2 !}, then we write ^w = ^w1w2:::. These sequences are called ^!-words. For

w 2 , ^w! denotes the ^!-word ^{w :w ::::}. We put ¹ = ^!. The elements of ¹ are called ¹-words. We dene the catenation of two

1-words ^uv by using the above denition for ^{uv 2} and putting

u:v=^u1u2:::un^v1v2:::, if^{u 2 v 2!}. For^u2!, the catenation is not dened.

Fora word^w=^w1w2:::wn,ⁿ1, we dene itslength as^jwj= ⁿ and for^{w 2!} we put ^jwj=^!. Finally we put ^{j j}= 0.

For a ^{w 2!} we dene the set of left fractions of ^w: If (^w) =^{fu2 jw}=^u:v, ^v2!g.

A subset of is called alanguage, a subset of ^! an ^!-language and a subset of ¹ an ¹-language.

For an innite sequence ^q = ^q0q1q2::: of elements of a nite set ^Q we dene In(^q) as the set of all the elements of ^Q which occur innitely many times in^q.

In the sequel, we will use the following evident assertion: For an arbitrary sequence ^s1s2:::sk, ^k 1 of elements of In(^q), there are indices ^{i1 <i2 <:::<i}k such that ^sj =^qi^j, 1^{j k}.

A graph is a triple^D= (^UH) where ^U is a nite set of nodes,

H is a nite set of arcs and : ^{H ! U U} is an incidence mapping. A graph ^D0 = (^U00H0) is a subgraph of a graph ^D = (^UH) if

U 0

UH 0

H and ⁰ :^{H0 !U0 U0} is a restriction of on ^H. For

V U, we say that ^DV = (^V0H0) is the subgraph of ^D induced by V if ^H0 is a maximum subset of ^H such that (^h) ^{2 V V} for every

h2H

0 and ⁰ is a restriction of on ^H0.

A trace in a graph ^D = (^UH) is an alternating sequence of nodes and arcs^u0a1u1a2:::an^un,ⁿ1 where(^ai) = (^ui^;1ui), 1 ^{i n}. We say that a graph ^D = (^UH) is strong if, for every

uv2U, there is a trace from ^u to ^v.

In proofs wewilluse the followingobviousassertion: ^D= (^UH) is strong i, for every ^{uv 2 U}, there is a trace in ^D starting in ^u, ending in ^v and containing all nodes of ^U.

3.

¹

-regular languages

Denition 3.1.

We say that a ve-tuple ^A = (^Qq0F) is a - nite deterministic acceptor or, shortly, an acceptor if ^Q is a nite set of states, is an alphabet, : ^{Q ! Q} is a transition function,

q 0

2 Q is the initial state and ^{F Q} is a set of nal states. For ^{w 2}

2 ^w = ^a1:a2:::an, ⁿ 0, a sequence ^q(^w) = ^{q0q1q2::: q}n is called the run of ^Aon ^w if^qi =(^qi^;1ai), 1ⁱⁿ. We put (^w) =

=^qn. If (^w) ^2F then we say that ^A accepts ^w. The set of all words accepted by ^Ais denoted by ^L(^A). A language^L is calledregular if ^L=^L(^A) for an acceptor ^A.

Denition 3.2.

We say that a ve-tuple ^A = (^Qq0) is a - nite deterministic ^!-acceptor or, shortly, an ^!-acceptor if^Q is a nite set of states, is an alphabet, : ^{Q ! Q} is a transition func- tion, ^{q0 2 Q} is the initial state and 2^Q is a system of subsets of innitely many times occurring states. For ^{w 2 !}, ^w = ^a1:a2::: a sequence ^q(^w) = ^q0q1q2::: is called the run of ^A on ^w if ^qi =

=(^qi^;1ai), 1 ⁱ. We put ^!(^w) = In(^q(^w)). If ^!(^w) ² then we say that ^A accepts ^w. The set of all words accepted by ^A is denoted by ^L(^A). An^!-language^{L !} is called^!-regular if^L=^L(^A) for an

!-acceptor ^A.

Note 3.3.

Clearly, for a ^{w 2 !} the run of an acceptor on ^w is also dened and so is the run of an ^!-acceptor on a ^w2 .

Denition 3.4.

An¹-language^L iscalled¹-regularifa regular language^LF and an ^!-regular language ^L! ^! exist such that

L=^LF ^L!.

Denition 3.5.

We say that a six-tuple ^A = (^Qq0F ) is a nite deterministic ¹-acceptor or, shortly, an ¹-acceptor if^Q is a - nite set of states, is an alphabet, : ^{Q ! Q} is a transition function, ^{q0 2 Q} is the initial state, ^{F Q} is a set of nal states and 2^Q is a system of subsets of innitely many times occurring states.

For^w21 we dene therunof^Aon^wusing either Denition 3.1 if ^{w 2} or Denition 3.2 if ^{w 2 !}. Similarly, we put ¹(^w) =

= (^w) or ¹(^w) = ^!(^w) depending on whether ^{w 2} or ^{w 2 !}. If¹(^w)^{2 F}, then we say that^Aaccepts^w. The set of all¹-words accepted by^Ais denoted by^L(^A), the set of all^!-words accepted by ^A is denoted by ^L!(^A) and the set of all words accepted by ^Ais denoted by^LF(^A).

Denition 3.6.

Let ^A= (^Qq0F ) be an ¹-acceptor. We say that ^G(^A) = (^QH) is the transition graph of ^A if

H = (^qi^aqj)^qi^qj ^2Qa2qj =(^qi^a) (^qi^aqj) = (^qi^qj)^: For a ^{P Q}, we denote by ^G(^AP) the subgraph of the transition graph of ^Ainduced by ^P.

Theorem 3.7.

Let ^{L 1} be an ¹-regular language. Then there exists an ¹-acceptor ^A such that ^L=^L1(^A).

Proof.

We have ^L = ^LF ^L! where ^LF is regular and ^L!

^! is ^!-regular. This means that ^LF = ^L(^B)^L! = ^L(^C) where

B = (^{P p0G}) is an acceptor and ^C = (^{R r0}) is an ^!- acceptor. Let us construct an ¹-acceptor ^A = (^Qq0F ) by putting ^Q = ^{P R}, ^q0 = (^p0r0), ((^pr)^a) = ((^pa) (^ra)) and

F =^f(^pr)^2Qjp2Gg. To construct let us consider^{w 2L}!. Let (1) ^p(^w) =^p0p1p2:::

be the run of ^B on ^w and

(2) ^r(^w) =^r0r1r2::: the run of^C on^w. Put

(3) ^q(^w) = (^p0r0)(^p1r1)(^p2r2)^:::

and dene = ^fIn(^q(^w)) ^jw2L!^g. is nite since, for every^w2L!, In(^q(^w)) ^Q. Let ^{w 2 L}. For a ^{w 2 L}F we have (^w) ^{2 G}, which means that ¹(^w) ^{2 F} and thus ^{w 2 LF}(^A). If ^{w 2 L}!, then, using the notation (1), (2) and (3), we see that In(^q(^w)) ² and thus, since clearly¹(^w) = In(^q(^w)), we get^{w 2L!}(^A).

To prove the inverse inclusion ^L1(^A) ^L let us rst take a ^{w 2}

2 LF(^A). This gives us a run of ^A on ^w: (^p0r0)(^p1r1)(^p2r2)^:::

::: (^pk^rk) ^k 0, where ^pk ^2G. Then, of course,^p0p1p2:::pk

is a run of ^B on ^w and ^{w 2 L}(^B) = ^LF. If, on the other hand,

w 2 L!(^A), we get the run of ^B on ^w: ^p(^w) = ^p0p1p2:::, the run of ^C on ^w: ^r(^w) = ^r0r1r2::: and the run of ^A on ^w: ^q(^w) =

=(^p0r0)(^p1r1)(^p2r2)^::: with ¹(^w)² . This means that there is a ^{w0 2L}(^C) such that

(4) In(^q(^w)) = In(^q(^w0))

where again ^p(^w0) = ^p0p01p02::: is the run of ^B on ^w, ^r(^w0) =

= ^r0r10r20::: is the run of ^C on ^w and ^q(^w0) = (^p0r0)(^p01r10) (^p02r02)^::: is the run of ^A on ^w. Let ^{s 2} In(^r(^w)). This means that

s occurs innitely many times in ^r(^w) and thus a ^pi exists such that (^pi^s) occurs innitely many times in^q(^w) or (^pi^s)²In(^q(^w)) and (4) gives us (^pi^s)²In(^q(^w0)). Then^smust occur innitely many times in

r(^w0), which implies ^s2 In(^r(^w0)) and In(^r(^w)) In(^r(^w0)). However In(^r(^w0))In(^r(^w)) can be proved in much the sameway. The equality In(^r(^w)) = In(^r(^w0)) then implies^w2L(^C) =^L!.

4. Limit

¹

-regular languages

Denition 4.1.

Let^L . Put lim^L=^{fw2 !j} card(lf(^w)^\L) =

= ^{! g}. The operator lim maps the set of all languages over into the set of all^!-languages over .

Note 4.2.

In 1] this operator is denoted by ^L and in 8] it is called

-limit. We use the notation as introduced in 2] and 6].

Lemma 4.3.

^{Let w2!} and ^L . Then ^w2lim^L i a sequence

w 1

w 2

::: of words from ^L exists such that

jwi ^j<jwj ^ji<jwi ²lf(^w)ⁱ1^:

Proof.

The proof follows directly from Def. 4.1.

Denition 4.4.

We say that an ¹-acceptor ^A = (^Qq0F ) is concise if ^LF(^A) ⁶=^L!(^A) ⁶= and, for any ^A0 = (^Qq0F0),

A

00 = (^{Qq0F 00}) where ^{F0 F}, ⁰⁰ , we have ^LF(^A0)

LF(^A), ^L!(^A00)^L!(^A)^:

Lemma 4.5.

Let ^A= (^Qq0F )be a concise ¹-acceptor. Then the following conditions are equivalent:

1. lim^LF(^A) ^L!(^A)

2. if, for an ^{S Q}, ^G(^AS) is strong and ^{S\F 6}=, then ^{S 2}.

Proof.

Let the rst condition hold and let ^{S Q} be such that ^G(^AS) is strong and ^{S\F 6}=. Let ^{f 2 S\F}. Since ^A is concise, there is a word^u2LF(^A) such that ¹(^u) =^f. ^G(^AS) being strong and^{f 2S} implies that there is a trace in^G(^AS)

c 1

(^c1a1c2)^c2(^c2a2c3)^::: (^ck^;1ak^;1ck)^ck ^{k >}1 such that it contains all the nodes of ^G(^AS) and ^c1 =^ck =^f. Let us now consider a sequence of words ^w1w2::: where ^wi = ^u:(^a1:a2:::

:::ak^;1)ⁱ and an ^!-word ^w=^u:(^a1a2:::ak^;1)^!. It is easy to see that

wi ^{2 L}F(^A)^wi ² lf(^w), ⁱ 1 and ^{j w}i ^{j<j w}j ^{ji < j}, which, by Lemma 4.3, implies^{w 2} lim^LF(^A). It is also obvious that ^fc1c2:::

::: ck^g is exactly the set of states occurring innitely many times in the run of ^Aon ^w and thus ¹(^w) =^S. However, by the assumption,

w2L!(^A) and thus ^{S 2}.

Let the second condition hold and^w2lim^LF(^A). By Lemma 4.3, we get a sequence of words ^w1w2:::wi ² lf(^w), ⁱ 1 such that

j wi ^{j<j w}j ^j, ^{i < j}. Let us consider an innite sequence of states from ^F

(5) ^{f1f2::: f}i =¹(^wi) ⁱ1^:

Since^F is nite, there is an^f which occurs innitely many times in (5).

Denote by

(6) ^q(^w) =^q0q1q2:::

the run of ^Aon ^w. Since, clearly, (5) is a subsequence of (6), we have

f 2 In(^q(^w)). ^G(^AIn(^q(^w)) is strong and ^{j w}i ^{j<j w}j ^j implies that it has at least one arc and so we get In(^q(^w)) ² by the assumption and nally^{w2 L!}(^A).

Lemma 4.6.

Let ^A= (^Qq0F )be a concise ¹-acceptor. Then the following conditions are equivalent:

1. lim^LF(^A) ^L!(^A)

2. ^Fi^{\F 6}= for every ^Fi ².

Proof.

Let the rst condition hold and let ^Fi ² . As ^A is concise, there exists a ^{w 2 L!}(^A) such that ¹(^w) = ^Fi. By the assumption then ^{w 2} lim^LF(^A) and, by Lemma 4.3, there exists a sequence of words

w 1

w 2

::: wi ²lf(^w) ^wi^2LF(^A) ⁱ1

such that ^jwi ^j<jwj ^ji<j. Thus we have¹(^wi)^{2F i}1 and since

F is nite, there must be an ^{f 2F} which occurs innitely many times in the sequence

(7) ¹(^w1)¹(^w2)^{::: :} Let

(8) ^q(^w) =^q0q1q2:::

be the run of^A on^w. It is easy to see that (7) is a subsequence of (8), which means that ^{f 2} In((^q(^w)) =¹(^w) = ^Fi. Therefore ^{F \F}i ⁶= and the second condition holds.

If the second condition holds and ^w2L!(^A), then ¹(^w) = ^Fi²

2 . Since^Fi^{\F 6}=, there exists an^{f 2F}i^\F which occurs innitely many times in the run of ^A on^w and thus there is a sequence

w 1

w 2

::: wi²lf(^w)^wi ^2LF(^A) ⁱ1

such that^{j w}i^j<jwj ^ji<j. Then, by Lemma 4.3, ^w2lim^LF(^A).

Denition 4.7.

Let ^D = (^UH) be a graph. For every ^{v 2 U}, we dene a system of subsets of ^U: (^{D v}) = ^{fV U jv 2 V ^G}(^{D V}) is strong^g. For a ^{W U}, we put (^{D W}) =_v^S

2W(^{D v}).

Theorem 4.8.

^{Let A}= (^QF ) be a concise ¹-acceptor. Then the following conditions are equivalent:

1. lim^LF(^A) =^L!(^A) 2. = (^G(^A)^F).

Proof.

Let the rst condition hold and^Fi ². Then^G(^AFi) is strong since^Aisconcise. By Lemma 4.6 we have^Fi^{\F 6}=with an^{f 2F}i^\F

such that ^Fi ² (^G(^A)^f). This means that ^Fi ² (^G(^A)^F). For an

Fi ² (^G(^A)^F), ^G(^AFi) is strong and ^Fi^{\F 6}= . Thus, by Lemma 4.5, we get ^Fi ².

If = (^G(^A)^F), then, for every ^{S Q} such that ^G(^AS) is strong and ^{S \F 6}= , ^{S 2} (^G(^A)^F) = and, by Lemma 4.5, lim^LF(^A) ^L!(^A). Next if ^Fi ² , then ^Fi ² (^G(^A)^F) implies

Fi^{\F 6}= and, by Lemma 4.6, we get ^L!(^A)lim^LF(^A).

References

1] DAVIS, M.: Innitary Games of Perfect Information, in: Advances in Game theory, Princeton Univ. Press, Princeton N. J. 1964, 89{101.

2] EILENBERG, S.: Automata, Languages and Machines, Volume A, New York, Academic Press 1974.

3] GRODZKI, Z.: The^k-machines, Bull. Acad. Polon. Sci. Ser. Sci. Math. As- tronom. Phys.,¹⁸/7 (1970), 399{402.

4] KWASOWIEC, S.: Generable Sets,Information and Control¹⁷(1970), 257{

264.

5] MEZNIK, I.: ^G-machines and Generable Sets, Information and Control ²⁰ (1972), No 5, 499{509.

6] NOVOTNY, M.: Sets Constructed by Acceptors, Information and Control,

26(1974), 116{133.

7] PAWLAK, Z.: Stored Program Computers,Algorytmy¹⁰(1969), 7{22.

8] STEIGER, L.: Research in the Theory of^!-languages,J. Inf. Process. Cybern.

EIK 8/9²³(1987), 415{439.

9] STEIGER, L.: Hierarchies of Recursive ^!-languages, Elektron. Inf. Verarb.

Kybern. EIK 5/6²²(1986), 219{241.