• Nu S-Au Găsit Rezultate

View of Some observations concerning the algebraic treating of the formal languages

N/A
N/A
Protected

Academic year: 2022

Share "View of Some observations concerning the algebraic treating of the formal languages"

Copied!
12
0
0

Text complet

(1)

128 loN RAS,4.

I

MATHEMATICA

_

REVUE D'ANALYSE NUMÉRIAÚE ET DE TI.IEORIE DE L'APPROXIMATION

BIRLIOGRAPIIIÞ I,'AI"JALYSE NUIVIERIQUII]

ET

T-A T}IEORITì

DE

L'APPROXIMA'Í'ION

Torne 1+,

2,

1975,

pp.

t79

-

200

[1] Àr a m a, O., Proþrietdlí þriui+rd ntonolouia giru.l'tti þoliøoøtnelov ltti S' N. B.ERNS?-E-fN çd aþli,carea lor la stud'iul. øþroùrnärii futtc/iilor. Studii qi Cerc. (Cluj), \¡IIIr nr.

3-4, 195 210 (1es7).

[2] Popoviciu, Elena, Teo.yemc d,e med,ic din ønaliza ntalemali'cd' çi lcgã'twra lor cr,t

teori.ø interþold"vii. Éditura Dacia, Cluj (1972)'

[3] Popoviciu, .fiberiu, Sur !,e reste d,ans aerta'ines formules linéaives tl'øþþroxirnatiott de I'analyse. Mathematica (Cluj), 1 (24), 95-143 (1959).

t4l Rényi, Alf récl, Probøbility Theory. Akadénriai Kiadó, Budapest, 1970.

l5) Z i e gl e r, Z v i, Lineøy Aþþroxímøtion sntl Generalizer) Conuexily. J. Äpproximation Theory, 1, 420-443 (1968).

Reçu le 25. V. 1976.

SOME OBSERVATIONS CONCERNING THE ALGEBRAIC

TREATING OF THE FORMAI-. I,ANGUAGES

by 1'EODOR RUS (Cluj

-

Napoca)

'lhe

necessity

of a formal

device suitable for solving the problems of

relaiions

between programming languages

and

betu'een

them and

com-

puting

systems, becomes

very

urgent. T'he paper

is an atternpt on

this

way. Having in

vicrv on o11e side

the form of

$'ord. free strüctures

of

the

programning

languages, generatecl

by their data

base structures,

pfimi- tive

operations and control seqllences, using some syntactical rules, given

by

operator schemes,

similar to te

operations

in a

word free algebra, and on

the

other side

the

observations,

the

operations schemes

in this

case are concerning

the

heterogeneotls operations,

irr the

paper we have the follo-

w1119 prlfposes :

l,

Oiganize

a formal

language

in the form of

heterogeneous word

free

algebra, o11 levels.

2, A formal

clefinition

of the

semantic clomain associatecl

to

a formal language.

- 3.

-To give a way of formal

representation

of

stlch ¿t

strtlcture in

an

othcr

one, r,vhich generalises

the notion of

homomorphism,

for a

formal

definition of

semantic preservillg

translation

algoritlims.

The

solutions

of the

above problems

are

presented

irr

sectioLTs 2,3.

Section

I is

devoted

to the definition of the formal

language

by

means

of

X-categories, used-

in

sequel.

1, A

CATEGORIAI-/

CHARACTERIZATION OF THE

FORMAI, LANGUAGES

l.l.

General considcrations

on the relvriting

systent

The

pair (t, P) is a rewriting

systeil. (semi-l'hue system)

when I

is

an

alphabet

aàd P'is a

set

of productions. (), P) is an

indexed rewri-

ting

system

when P is an injection from an initial

segment

of

nals¡"1

(2)

1sé

numbers

to

X* X

X*. In this way

every

production

o(

-r I e P is

distin-

guishable

by its

index, so

that P(n):

d

+p

can be

written

^, o3 p.

The

relation -> can be extend.ed.

to

=+

by

concatenation

in the following way:

If 0, t|l e >*,0:"{F, ü:vpp

and.

ø-PeP then0+{.,Let

us

consid.er

the transitive reflexive closure

of

+ and

clenote

it

bV

å.

For V*

= 2*,

V7

c 2, the quadruple (>*,

V¡¡,

Vy, P) will

be

called grammar and the

language generated

by G: (>*,

VN,

Vr,

P)

is

defined

as

follows:

L(G)

: {u e Vi ll o = V*,

o-!7u}

The

extensions

of the

relations definecl

by P from

--+ to

+

and to -!2 d.efine

a

category.

Let us

denote

this

category

by

F.

The objects O of

F

are

the

elements

of 2*.

The set

M of

morphisms

of F is

defined

by:

(i). the length zero

derivatiorrs,

aj>

u", d.

e !*

are identities

in

MI,

denoted

by

1o.

(ii). If þ = P

then

þ is

considered'

as a

morphism

of length I

and

belongs

to M.

So,

P c M.

When P

is

an indexed set,

then (n,

a

!>

pS

e

e Pand

"39 e

A4.

îhe

domain of.

q.!, p will

be ø

and the

cod.omain

or a3 B will be

p.

(iii) For

every

pair of

id.entities

in M, 1*, lu and every

morphism

,.3þeM the morphism 1u*(a39)*

1"

eM

and

is

determined uni-

luely by

¡-r,,

v

ancL o.

3 9,

where

x is the

concafenation

of

morphisms.

(iv). For

each

x, y e M

such

that

cod.omain

of ø

belongs

to

the domain

of y is

defined

the

cornposition

yofr,

ãrLd

y"x e Il[.

From

tLis

d.efinition

it

follows

that

each morphism

in M is

equivalent

to

a derivation

in (>, P)

from

its

domain

to its

codomain. Then,

for

two ,,bjects o(, P

= Xx, Ifom (a,

p)

is the

set

of all

derivations

from e to

p,

or the set of

rnorphisms

from a to

p,

Following norz fl],nnNsoN[3], cnmrrrns [2], onthe set of

mor- phisms

from a to p

can

be

defined

a

congruence

relation -

and

for

stu-

dying the syntactical structure defined by (), P) in )* the

category

Fl-: (>*,Ml-) can be

considered.

The, category F/- is

aÍL X-cate-

gory

as

it

was d,efined.

by norz ll]. From this

reason and because

X*

categories

will be

used

in the

sequel we

shall

redefine

it.

1.2,

The notioil of

X-cal;egorx

the

systern

X:

(O, 14, Q,

Z, ., *) is

a X-catcgory

if the

following properties

hold:

(i).

O and

M

are sets,

Q

and.

Z

are functions, Q,

Z: M

->

O; Q will be

called.

domain function

and

Z will be

called codomain function.

B

soME

oBsERVArtoNS

181

(ii). . is a partial

operation

on M,

o

:

Mz ->

M,

called composition, and

is

defined

in the

following

way: if (x, y) = Mz

then

y

o

x is

definecl

iff 8U) : Z(x) and the following

equalities

take

place:

QU

. ,) :

Q@),

Z(y

" x)

:

Z(y)

(iiÐ. . is

associative where

it is

defined.

(iv). For

each

object

d:

e

O

there

exists a-uniquely determined

loe

e

/14 called

identity on d,

so

that for

every

y,* = M

f.or

which

ø o 1o

and

1o

o! are defined

alnd

Z(1,):Q(x),

0(1")

: Z(y) t}ren x"ln- i

and looy:y.

(v). The

algebraic systems (O,

*, Ìt),

(JW,

*, 1¡) are

monoids,

Âe )* is

empty string

in X*

and Q,

Z: (M, 'r,

1i,) -+ (O,

*, z\) aÍe

monoid homomorphisms.

(vi). For every *y

x2,

lr lz e M so that

Q(yr)

: Z(*,), i :

l,1Z

the following identity takes

place:

(yr*

yr) "

(xrx

xr)

: (!ro

xr)

* (!r.

xr)

(vii), For

each

ln,

7u

e M,

lu x

lu:

lu*u

Now, given

a

rewriting saystem

(>,

P)

the

corresponding X-category

is

denoted 7>y

D: (>*, M,

Q,

2,", *)

where

()*,

*,

Â) is the

free monoid generated

by

>

the notation Hom, (a, p) for the

set

of all

morphisms

from a to p in the

category

D we

have:

1.

ø

3> p is

equivalent

to

Hom1r(a,

þ) + ø

2.V* c X*,

Vy

c 2, G: (2*,V*,Vr, P) then the

language generated.

by"C is L(G):{ueV$llxeM, Q@)=V*, Z(x):p¡

3, rf

p

e x* then the

syntactical structures

of g

are

v*Homoþ,

þ)

4. the set of all

syntactical structures

of the

language is

s(:*,

r/N,

vr, P) : u Q.

Homoþ,u)

v\- o'v*

For the study of

some

relations

between languages

the notion

of

X-functor is

wanted.

In

ord.er

to

define

lhat, let X¡ :

(O¡,

M¡, Z¡, ",

*)

j :

1,2

be two

X-categories.

A pair of functions

11

: (hr, h*) will

be

called.

X-functor if the following

properties

take

place:

(i). ho:

(Or,

x, ¡) +

(Or,

*, A)

and

(iù. h*: (Mr,'r, l¡) n (Mr, x,

1¡)

are

monoid homomorphisrns.

iÈéoon iiúé 2

(3)

SOME OBSERVÄTIONs 183

TEODoR RUS 4

(iii). ã'.(Or,

M,,, Q,

Z, ") -

(Or,

Mr,

Qr,

Zr, ") is a functor, that

is

(iii1).

If a e

Or

then h*(1"):

1¿o(o)

(iiir), For

each

y, xeM sothat )toxis

defined

h*(y"x):h*(y)"h*(x) (iiir). The following

diagrams commute

catcgory associated

to a rewriting

sys-tem

(>' P)'Thcn an

interpretatiou

;î" ð'ï, -ï"t i. r

""X-"åiottctor"

1-:

D -' àet so that for

every

o ' ?, T\rí*'ä ^;i it"¡ + rf -*fr"t"

^ is the identity set

according

to

the

oueration

X.

"u"'îåiäuâ D is freely

generated

by-(ì, p) a particular

interpretation

¡

is

-a"t"tmined by the

fãllorving conditions :

(i). For

each

øe>, I

(ø)

*Ø, I(ø) eV'

(ii).Foreachø*p€ P, I(a'*P) :1(P) 4I(a)'f eF

The

above considerations $¡ere

la *

ß).

That is

because the

ìir... it-r"

svntactical structur

by G: (>*, VN, Vr, P)

is

uÁe

D tò define the

langua

of the

language.

I,et now

7!)1,

Isz c L(G) be given' \\/hat kind of relations

can r ¡e

d.efine between

u,

and ø,

? Of

cours

morohisms

'Th" ittt"tttal from

IvI.

structure of

the

G: (Ð*, V*, Vr, P) can be

stud

role bf

symbols-

ftonr V,

d:uring,

will

lead.

us to an

overlaPPing of

a

1eve1

will be the set of

generato

must fol1ow tfre

naiurái way'of

lauguage

defi'ition,

which

is

pointed' out

ü;;;;t;atural oiãititi"iáf

languãge."The ptinciples

in this

overlapping

are the following:

(i).

There

is a first level of I dictionary' ll !þ"

"r."'ãi "ãã"irl-f""g"ãg"r-ih" ai"t dictionarv of

.the

lansuase and

in tü8-""'sà of progra it is its

basic data strtictu"re,

primitive

operations and'

tiil. Let the

leveis

0,1,.. ., i - I be built'

The

level , (if it

exists)

*i11

f,; ¡irlt Ìiom the

elements

of

levels

0,1,..., i - l iu a

recursrvcty way,

by the rules

specified

by the

gtammat'

782 5

zt

-0

i'

11t

t"

(;,

luo

t4,

I

0, c.

Ii

0

Qe.

Fig. I

The

pair ¡7:

(h,rr, /zo)

is a

cofunctor

if

instead

of (iiir) and (iiir)

we consider'

(äi|).

tono(1t"x)

: h*(x)"lrr(1,), for ever¡' x, y

e

M fot which yox

is

defined.

(iiii). The follorving

diagrams comute

/L

I'ig. B

1.3.

Thc notion of

interpretation

of a

lang¡uago

For

semantic

definition of a

language vve sha1l consider

the

notion

(4)

TEODOR RUS SOME OBSERVATTONS 185

184 6 7

From these

observations

follows that in the set

,44

of

syntactical structures

of the

ele_ments

of the

language

must be

definecl

an

ord.ering

relation which will

decompose

the

set

M in

classes following

the

princi"-

ples (i) and

(ii).

The

overlapping

of the

language

will

show

us that

\Me are able to associate

to a

language

an internal

algebrical

structure

richer

than that of x-category. This

structure

rvill

be defined using

the notion of free )-

algebra defined

by nrccrns l5l.

2. THD OVERI,APPING OIi A FORMAI/

I.ANGUAGB 2.1. T'he gcneral eonsitlerations

on the

decornposition

of P

For

'the definition of the

overlapping discussecl above we sha1l start

with

general

definition of the

languz

g" by

means

of a rewriting

system

(P, fl.

S_9,

f9r

Vto

= 4*, .Vr c ) we

consider

the gramm"t G: (l*, Yr, Vr, P). Our

hypothesis

will be that V* c X and the

grarnmàr G

is a

context-free grammar.

From $ 1,2

rve

liâve:

3(>l*, zN, v,, P): u u Hom, (o, ,)

QevT aevN

L(G)

: {u e Vflfx e X[,

Q@)

= V*, Z(x) :

ø]

The classification of. t_he prod.uction set P which

will

supply an overlappirrg

of the

langugge

will be-relating only to the set s(>*; V*, Vr, eiin{t

is, only to that part of M "of

morphisms

which

can

be

considered. as svirtactical'struc-

n

ordering rela

in a finite

set

1 y in the

ear

For that

we consider

the

grarnntar

G: (>*, V*, Vr, P) not

having

just

one

1{om. Each

symbol

from V*

can

be

considere¿

ai

axiorn likõ

in RUS t6]. That

does

not

change

the fact that

G

is

context-free in a classical

way,

because there exists

a

context-free grammar

G' with just

one axiom so

that L(G): L(G').This

idea is

very na¡¡¡al havingi1

view

the

prograrnming language. So,

not

every expression

in a

programming language

is a

program,

but

belongs

to the

language. For instãnce, the ide,ntifiers are-no programs

but

belong

to the

language

in

which

they

are

defined.

In_this

way the idea

of

overlápping

of

thé language can be

ieali-

zed.

in

the following r /ay :

(i).

The

first

level of the language is Zo(G) and

is

defined.by

the

strin- gs

u e

L(G) for which we have : iL

u =

Lo(G)

that

means

that there

exists

A -w e P

and

A e

Vw,

u e Vï.

I.et Ms be the set of

firorphisms

{rom M(L) which

are syntactical 1 be

built,

denoted

bv Io(G),

L'.(G)'

built by that

that

means

can

be

repre- orphisms from

Mo, "' Thã Mr,

effectivå i"ãS¡Latiot,

..', M¡-1,

M¡.

of (i) and (ii)

above will_

be made by

an

ord."ring relation

¿"fì""ã o"

the pòrîerset

di'p. This

lead.

to a

decomposi-

tion

of "P

in

classes

of

subsets. Such classes were considered'

by

,SAI,OMAA

lTlfarestrictiononthesetofd.erivationswith

a c in

Salor

crit is

PaPer

a rnatrix

grammaÍ

or an

ordered- according

tã the

ordering d.efinition.

tions.

2,2. Tlne

all¡orithm for

dceomposition

of

F

in classes we shal1

nVr' þ:("'þ)

the

emPtY string.

I wherc l¡ = Vi

or

2, ..., n. By

Cat(þ)

is a

subset

of P

then

Vr, P)

and,

L(G) + Ø tloen

tkeYe

tkat

þrr(þ) =

V¡t' þY,(þ)

= Vi' that-there

exists

at least

oÍre u)

e

syntactical structure

ol a

derivation

That means that

there

is P e

P,

number

of

steps as above we sha1l find- the.production p'

---ihtootooi.

ll

L(G)

then there ex'ists

qn uryiqu^e-- 9?

the iet P in

the"

tuùtttt'

Po,

Pt, .. ', P,

so that tke

fol'l'

'itions

take þl,ace :

(i). ry þ' P

ønd'

þ e

Po tken CøtQfl

:g¡'

(5)

186

(1ù.

If þ = P; fot' i: l, 2, ..,, n

th,en

g soME oBSERVA'rIoNS 787

P¿*, (at

i.he That

means

to

perform

,, I Þ,*, U wili

be cleaned

from

C'

î trr" åilgoii

DECS'

rf the

condition

e

next stlep

DECT'

DEC7.

Verily if all the

elements

of P1

are classifiecl.

For that

set

I to

1

+ l, I

:

: I I

1, ancl verifY

if

tions from P1 rvhich can be classified' ar

can be eliminated from P

because

language.

In this

case

set I to I -

tlre- algorithm is DEC9. If Pt *

r

been

built.

Then

performthe

operation

C::

PL

\U^ 4

j:o

and

algorithm

continue vgith

the

step DEC8.

DECS.

\/erify

the conclitiot

c :

Ø?

Irft

is true the

[ext

s-t9r is. DEcg because

all

elements

of Pl

are classified.

If the

condition

is

false the next step

of the algorithm is

DEC6.

DECT.

set a

nerv

variabile N to 1, N:: I andbeginthe

classifica

tion of

P2.

DEC\T. \¡erify

1.he cond.ition P2

:Ø? Il it is true the algoritltry l:

comoletecl an,L

subslii ^rl" Po, Pt,

.

", Pn

r"'here n'

is the

va'lue

of N

If

Pz

: Ø is

false

it follol's the

step DËCl1'

DECI1.

Choosc an

arbitrary

ele nent

þ = P'and build the

correspon-

cling-"1eme'111

p" br;;;.iitg

rrom

þrr(þ) ail

symbols equal

with

þrL(þ)' DEC12. Set -I

to

zeto,

I'.:0

DEC13. VerifY

if Cù (þ*) : Ø or iÎ

Cat(þ*)

c. U n'l"i

þr,(q)

j:o

If at

lecst one

of

thcsc tr,r-o conclition hoid, tlLerr

P¡+t" :

Po

rt-U/

r1h-ere

i is the

value

of 1,

ancl 7) rvi11

bc

crasccl

from

P2.

Next

step _of algorithm

is Dlici0. If ro

one

of thc

aborre condition ho1d,

the algorithm will

look

up {o, a

nc\\¡ su.bset

Íor

classì1i1'1"g-þ

setilg I to I +

1,

!:: I )-

1' and choosing

the ncxt

stcp

to

be

f,,flCtã.'If theie

afe no sets

for

classifying

/,

tlren is Tu1fi11ec1

I

==

Ñ

utd

þ

can

be

erased

from

P2 because

there

are no

å1.-""t0

ut

= L(G)

r.r,hich óan

be

obtaine-d

by

using

/. In this

case the

algorithm contìuue

l'ith

DEC10.

The

operatìons usccl

to DEC

clescr-iption can be .easlly pr_ogrammed

i" ."..,

asöemb11, languagc

r¡r I,ISP-likè

language.

The flow

diagrarn of

DEC is

presentecl

in figure

1.

Cat(b\

c

TEODOR RT'S

t,

þv,(q)

u þr'(þ)

B

quUPj j:0

(iii). Q

tl

Pn. e, P, n

: Ø,

i, +

j

i:o

(ir'.).

Th,e decontt>osition. Po,

Pr, ...,

Pn í,s th,e

finest

one zaitk tlte bigest cørclinølity

of

tloe classes Po,

Pr,

. .

.,

Pn

uhich

has the þroþerties

(i)

-

(iii) .

,,(r,),

If ue

considcr the grømmat' G'

: (2*, V*, Vr, P')

uh,ere

P' : : U

P¿ then

it

fottows L(G)

:

L(G').

Proof

.

The demonstration of

this

theorem

will

be made

by

describing

the algorithm

¡¡'hich rvi11 dccompose

P

so

that (i) - (") hold. For that

1et

DEC be the

name

of the algorithn. The

steps

of this algorithm will

be denoted

by

DEC followed

by

digits.

DECI

.

Set index

I to

zero,

I

:

: 0. It

rvi11 count the number of classes.

DEC2. Decompose

the set P in two subscts

PL

and P2

so

that P :

PL

\)

P2,

Pr î

Pz

: Ø

accordtng

to the

following definition:

P' : =P lþr'(þ)

æ cøt(þ)}

P' : =

P

I þr,(þ) =

cat(þ)}

DEC3. The

first

class

of P is

Po, Po

-

P1, and

is built by the

rela-

tion

Po

: U, = P'lþ/r(þ) = Vi\.

Observation:

From

lemrna

I it

follorn's

that

Po

*Ø,

DEC4.

I.ct

Pu,

Pr, ..., Pi,

be already

built.

Consider

the set C

de-

finerÌ b1' C :

:

P1'..

[J Pi

r'vhcre b1.

..

u,e have denoted

the

operation of

subtlaction nn r.ta.':n

DECí. \¡erify the conclition

C

:

Ø

? If this

conditioti

is true,

the

algorithm continuc rvith

DlìC7

; if the condition is

false,

the next

step

is

DEC6.

DEC6 Cat(p)

=qG l) Pj

i=o

Choose

an

ar1¡itrar)' e1elxeüt

þ - C

and

verifl' the

condition

V lrrr(q). If tliis

conditiorr

is true then we

have obtainect

(6)

.l: -0

é

Ì.,t1

€. ca/

(

P, =l

P2--ø L =y

¡

Q) s roP

DEC

U

i,.o

C:=C

c.p

U

C:--P/\ Pj

lr€-c

(, l'

1e¡t

Y{5

yE5

s Y{,t

1t SOMB OBSBRVATIONS iB0

Let

now

p' :ÜP¡

where

n isthevalue

of .ðy', and

G':(2*,

V¡¡,

Vr, P')' From the algoriihm

d:0 described above

it results that

L(G)

: f(G')¡

The other properties follows

from the

algorithrn description too.

Examplel X: {Xo, Xr., a, b, c}, V¡¡: {Xo, X},Vr: {ø,

b, c},

P :

{Xo -+

X¡X1,

Xo

-

øXob, XL -+ cXy, Xo

-

øb,

Xt'+

c)

Pt : {Xo

-> øb,

X,

-> c}

P' :

{Xo -+ XoX1, Xo

-

øXob,

Xr +

cXy}

In this

case

we have Po: Pr an . If

G0

: (Z*,

Vw,

Vr,

Po)

a :_{qb,

c},- L_(G)

7

: {ø"bic^l ¿(GJ: {a"b}

anð'

Lot

n:0

From

Lemrna

2. If u e L(G)

and' x

e

Homp(A,

u) is a

syntkacticøl' d'escriþ_-

ion of a,

so tkøt

for

ø þiuen

i', A = {þrr(þ)lþ = P¡)

then

for

each sub-

string u' of u,

Is

:

IsLT!)'uo,

so that u' =

L(G)

there-

is ø

syntacticøl' d'escriþt'ion y e Honor(B,

w')

uhere

Be

þr,(þ)

V =[JP,

j:0

This

result makes

it

posible

to

d.efine

the

overlaping

of the

language

Z(G)

as follows:

1. The first level of the

language

is

Zo(G) and. it,

is

generated by

Go: (2*,

VN,

Vr,

Po).

2. the

sécond leve1

of the

language

is Zt(G)

and,

it is

generated by

Gr: (2*,

V¡¡,

Vr, Po U Pr)

ì

i. The i-th level of the

language

is Z;(G)

and

it is

generated

by

G¡: (2*, V*, Vr, Po U Pl U ... u

P¿)

n.

The

n-th

(the last) leve1 of the language is

I(G,)

and

it is

generated

by G,: (X*,

VN,

Vr, Po

U

P, U ... U

Pr)

The-sets Po,

Pr, ...,

P¿,

.,., P,

are

the

subsets

of the set P

defi- ned.

by the

algorithm DEC, Now

it is

clear

that

r,,r'e have

(i)

¿d(c)

c

L¿+{G),

i:0, I, ..., n - | (ii)

¿,(G)

:

L(G)

According

to the

above relations between

the

levels

of the

language

Z(G) we can

d.efine

the

relations between

the

syntactical d.escriptions of

the

strings

of the

language.

I-,et us

denote

bV M(L) all

morphisms of Ftg. 1. Thø flout di,agrønt' o.f DEÇ

(7)

ieo TEODOR RUS

72

3,

'S-AI,GEBRA OF A

T'ORMAI,

I,ANGUAGË

3,1. ìS-algebras

set

ancl

a family eL(I) of

relations

on I, r = e(4 with the

properties

(it, ir, ..., i,, j) =,

follõrvJ

i:/

ì1" "l'","3i'îli "åf îå*

"

":,"î:t tï: Í

) can

be indexecl

by the n-arity

of

thcir

cornponents,

aQ) : l) O"(l),

e.(1)

: [J a,(¡)

rvtrere O(1)

is the

set

of all

operations

on 1, "

't

S lrgil'(I,

,!Ð,

!t F e(I) will be

called a retational algebra

on 1

and

a lrair U, A), q .

O(1)

s'ill

be callec1

a partial

algebra orr- 1.

I,et

us consider now a non

cnrtl'

set

f), Q n

1

: Ø sothat

Q

:

UC¿".

Art'

{l-structure

on

1 is

defincc

by a function

a :

o -- ll(-I) y,hich

upþti"u

{l,in8Ln¡r(I), n:0, 1, .... Inthis Yayasymbol.acts

under

the

mappi- ng ,t as an'(ít.

¡ l)-ary

relation on

1. If

each symbql

g =

Q,n,

n :0, l, aõts

und.er

d as an n-ary

operation,

theri (1, a) is

called

an

C)-partial algebra.

In this

case

ô e {I,,,

rou"

=

O(1)

(it, ir,

. .

., i,,, i) = .(o)

and u'e denote

this

operatiou

by iri, ... i,,a or i:tttz ...in6.

For a

given

non emty 1 and a

non

emty

set {ù,

and an

application ø : C) ->

St(I) the pair ) : (1,

,.)

is

ca1led

an

C)-scheme

or

operator sclte-

me

[5].

Lét

now

A

be a

family

of sets,

¿ :

{A¡}æ¡ indexed

by I.

We supposc

that for

each

o e

e)n,

n:0, 1,

eincl

each (ir, ir, ..., in, i) =

o,'o

is

given a function

-

Tlre

family A: (ti,i,,,.i,,:A¡,X {A¡)¡.¡ together

A¡,

X rvith .. . X all

A¡,,'--+

functions

A.¡. given

by a )-

scireme

will

be callecl an Q-algebra

with

the oper-ator scheme

X or

shortlr', )-algebra

In this

way

the notion of

algebra

is

defined

by

using heterogeneous operations defiued

by a given

operator scheme

). For that two

things

must be

precisecl :

(i)

, A

function

I"

->

I u'ith the

role

of

domain selector

of

operations defined

by the

scheme.

(ii). A

composition 1aw

for the

elements

of the

selectedsets

by

(i).

For

algebrical porposes

(i) and (ii)

are

quite

enough

to

charracterize

the structure

definecL

by operator scliene 2:

(1

,

ø),

on a family

of sets -4

: {A;\¡=¡. That

because

the problen

is not tosee

hor¡'the

opera-

tions

defined-

by

operator scherne are

conputed, but it is

enough

to

say

that for

each

o e

C), cocr

rvill

select

tlie

domaitt and coclomain

of

operation, so

that

(l). (r,, i2,

. .

.,

,i,,'

i) e

aa

(2).

(or, &2,

.,,,

&n)ra,i,¿,..,ini: atØz

,',

an6i,i,i...i,¡

for

each øo

e

Aih

h:1,2, ..., n

and.

øra, ... aori,i,...t¡ e

A¿

For the

algorithmic

point of I'iew this

clefinition must has

a

compie-

tion in the

sense

of indicating

how

the

operatiolls (ò¿,1:,.

..i*i

àr? computed.

That

means,

that from the algorithmic point of view it is not

enough

to say tlrat

n-tupl

.

(ør, ø2,

...,

a,,) belongs

to the

domain

of

cl¡,.¡,...;n¡.

It is

necessary

ãlso to indicate the way of

depending

of the

building process

of atør, , ,

Øn6í,i,...iui

by the values of

ã1, a2,

,..,

&rt:

lhat

õan be

better

seerr considering

this

process as

an algorithm

described' by

a

sequences

of

steps.

The order of the

execution steps

is given by

the values

of ør, ar,

. .

.,

&n rvhich

are data of the

algorithm,

In

the usual cases of operation

in

the numerical structures,

this

aspect

is not very

clear beacuse

the

numbers have

two

different determinations, On one side as syrnbolic names ancl on

the other

siclc as valucs

of

these

names. The value of a nurnber

is

predicated

by its

synrbolic

form, or

in.

otherwords, the value of a

nttmber

is irnplicitely

given

by its

symbolic representation.

If

rve consider

that

speaking about sets we use

the

nanle

sf their

elements, consielered. as t¡ariable

on

these sets,

then this

double irspect of

the

nanre and of tire value arise immecliately.

13 SoMr ous¡nvattoNs 1e1

x-category D which are syntactical

descriptions

of the

language. Then we have :

l'. The first

class ?f_ !!.(L)._d.enoted

bv MoØ) is the

same

with

po

2'. I1 the

classes

Mr(L), Mr(L), ..., MnØ) have

been

built,

then M,*t^(L,)

will be built by all

morphisms

from

E(2,1,,

Vn, Vr, p) wtth

the following

properties :

(i).-If x e M¡+t(Z) th91

thereexists

a

decomposition of

ø

according

to " and x

so

that x_- y{?}r, y

?_Pn.-r,

z e Mo u M, ... lJ

M¿11o1

,.l:.tr,_y

=X[.oU,Mr,t)

... u M¡tr

whcrc

y{i\z nr.a"s yoz or y*2.

(ii). If

l.(x)

is the length of x, that is, t"hd'íiumber of rules

íror,, Po,

!1, .:.,-P¡_\r

appllied

to build r, then l(x) > i + l.

The study of the morphism classes

Mo,

ll,[r,'

...,

JII,, r,r'i11 1eac1

to

some

methocls

of

s¡'n13-q1ical arralysis

using riormal

algorithm

thc

classes

Mo, Mþ .,.,

ilI

,,

shou,

us a kiucl õf

struc be clefined on

the

strings

of the

language.

This

structure bccl

by Mo, Mr, ..., M,, in

an

indireci

u'ay, can

be

clire

aical structrll'e on Z(G), definecl

b¡'

¿

,

o."

:nå,,Yîì'il'iîff ;i "ü*,å?

o, u -:

o(zar,

ur, ..., uu) =

L(G)

i1t

by

usirg a

free algebra scheme such a structurc

u,ill

be clclinedin

the next

secticin using

x-

algebras

delined by urcc;rNS t5l, for characterizing

heterogeneo-us algJbrical

structure, For this

reason rve shal1 begin thé next seciion

with

tËe defi-

nition of

)S-algebras rvhich are suitable structures

for

characterizirg the inf.ernal

structure of a

iarguage.

(8)

1,ô2 TEODOR RUS 14

;'

Ë,

The

above observations lead us

to a

generaTization

of the notion

of operator scheme,

that

arises

by

determining an operation under

the

follo- wing conditions :

(i). A

function

I"

--+

I

which

will

select

the

domain and codomain of operations.

- (ii).4

composition

law for the

elements

of the

selected sets

by

(i).

(iii).

A state word of the operation which u'i1l indicate the way

in

which the proôcss of building

thc

resùltis dependingbythe value of

the

operands.

on (iii)

1et us

Bisasetof

fl;,";r;,?ä'

A by

7,

types of the type of the

above construction

by

3.

Tleen one

ele

1,

2, 2, 3) is not

enough

for

showing

what this

element of _operator

scherir.e shõu1d

be 3) or in other fornr

((1,

2, 2),

(i1,

then, el

example

in

programming langirages. But we

try

to indicate a general scheme for this kind. of operations, using on one side the context-free grammars and

on the

other side )-alge- bras defiued

by nrccrxs

[5].

By an operator scheme XS we mean a pair (I

,

ø) where ø

is a

function

ø:O + O(I) x SI,

where

57'is a

given set

of

rvotcls,'charracterizing the selected operation

by

o., and called semantics selectors or state words.

In this

rvay

to

each

o O, will

correspond.

by a a triple (ir, ir,

. .

.,

i*)

in the

domain

of

toø,

(i) in the

coclomain

of

<,¡q and

s c ST of

oø.

I,et

rrorv

A : {A¿\;-¡ be a family of sets

indexed.

by 1 and a )

S

scheme

as

consiclerìed.' above,

Then for

co

e

C), we have

the

follo-wings

If. (i\, iz, ..., i,,) e D(oø), (i) =

R(<oa),

(tr, tr, ...,. s,+r)-<

S?(ora), where

Af D, R,

S?-'we have denoted respectively domain, codomain and.

state worcls

of the

operation coa,

then for each

ctn= A¿t (sra1, s2ct2,

.'.,

strarr, sto+t) crla

:

sLøLszttz , ,

.

srrarrsa4-1 ' belongs to'-' A¿.

In this

definition is

not

explici ;ely represented.

in the

result trecause sometimes

it

is represented by one of

the

senantic selectors

or state

words.

But

sometinres

it

is necessary

to explicit

thern

in the form of the

,,llame

of operation" or,rname of

resu1t".

In this

case

ô will be a

1abe1

of

the result ancl we sha1l be able

to

define operations on these names

too,

being able

in this

maner

to

have

an

algebrãical clescription

of the

algorithmic processes.

'Ihe form of

representing

of

these labels, when used,

will

be

o): s{L\szq.z...sra*snt1 or_

avoiding any

ambiguity

in_the lotm airir...-i"i.^

sLøLszaz. . .sra.*s,¡¡1.

In this way the

1abels becom thenselves operands of

thettype

ø.

Afamilyof

sets

¿: {Aa}r,=¡indexedbyl

together

with all

op_erations clcfined

by a

X5-operator-siheme,

)S: (1,

"),where u.:ç,

->

9(1) x

S7-

will

be called.

a

)S-algebra.

When

ST

:

Ø

then

ZS-algebra

is just a

X-algebla,

15 SoME obSERVATÍÔÑs 193

3.2.

ES-Algel;ra

assoeiatcti

to a

grammaÍ

. Let I

= (2", Vu, l'.x, lt)

be a given context-frce gràrltrriíì1', supplied

by a

semi-Thue systern

lX,

P-) a:nd

D: (t*,

X4,

q, Z, ",

r,¡

bc

X'-õate-

E9?

geuerated

by (>, P), The

language generated

by

G

is

defined by L(G)

:

{w

e v.i:llx e

ù!,.Q@)

= v*: zú) : *}.

As rvé have shown therê

is an

uniclue_clccompos;itio'of

P in thc

stibsetÁ

po, pr, ,..., p,

so

that

theorem

t

ho1d.

rlsing tliis.

dcc_omposition rve

shall

dèfirie

no*'in l1c¡

a structure

of

xs-algebra. tr'or

that, let

L1s use the following notions :

B¡, the index of G

we

shall

unclerstand

the set zr-indexecl by

its elements.

For

avoiciirrg

any

misunclersta:rding rve d.enote

"the index

-of

G

ÞV-!o

supposing

that

In is

a set of ilatural

numbers so

that the

following

hold:

(i). If i e Ic then there

exists

(ij) If i, j = 1", i -#_j, then A¡ = V*, A¡ #

Ai.

Given zr

prockction þ e P, /, : ("

"i jtrr(ü -

A,

g:

7

srArsrAr.,,suA,rs,,-¡1, s¡

Z.lT

ors¿ : i,

2::

,,,,à, rì+t

Ry þrvr(1)

rve sha1l denote

the se ., s,, s,+r) and

by

þyr*(þ) we sliall

clenote

the

secluence

(t!r, Ar,

. . .,

A*). By I(irrr*(þ)) we

denot-e

tLc

sí-rlrlcnce

(ir, ir, ..., .i,,) u'hcre

iu

is the

inclex o1 Ào in

1", lor

k -.- 1,

2,

, .

.,

11,.

For the

decomposition

of P in the

subsets

pn, pr, ..,,

pn

let

us

consider the Tollolving sets:

S,: l)

þt,nr(þ), O,

: U-r(þrr"

(1,)),

T, : l) r(þr,(þ)).

þ=Pi þ-Pi "

þ.Pi

It is

clear

that to

each

þ € P¡

we can associate

a tr

ere

o¡=.

O¡ sr= S,, t¡= T¿.The triple

(o,(l>), s¡(þ),

t¡(þ))

pe-

lqtion

scherne supplied

lry þ

.

oo(fl

catteci

aoäá

oD,

ta(þ) is called codomain of

thè opetãîion and

s;(p)

is

or

semantics selector

of the

operation.

I,et

now

Ð' :

{(on(þ), t¡(þ),

t,(Ð)l

on(Ð

= o¡,

s¡(þ)

=

S¡, to(þ)

-

7-i}

for a

given subset

P;, and

we

call it

opelator scheme

of the

subset

For the

grammar G we can consider

on:

i:0

Ú o¡, so:

i:o

ú t,, T":

i:o

ü 7,, ,o: ü

- i:0

,,

called respectively domains

of

operations supplied

by

G, state words or semantics selectors

of

operations supplied

by

G, codomain

of

operations supplied

by

G and operator scheme

of

operations supplied

by

G.-

be Pi.

6 - MathÈluatica

- Revue d'analyse uumórique et de lhéorie de l'approximatiotÌ

- Torue 4, No. 2/1g?5

(9)

1g4

ftóDoR

Rùs

16

E x e m p 1e

: I,et

G be

the

gÏal11mar

from the

exampl.e

in

2,2, where

,,r"

"ã*id"r ior X, the

inclex 1 ãncl

for X, the index 2. 'Ihen

rve have :

IG: {1, 2},

So

:

{øb,

c},

S,

: {(^,

^, ^,), (o' b)' þ, ^)}

oo

: {( ), ( )}, o, :

{(1,

2), (r), (2)}' r0: {(1),

(2)}

?1

: {(1),

(1),

(2)}, )o : {( ( )' (ot)'

(1)),

(( ), (')'

(z))}

>, :

{((1,

2), (^,^,^,),

(1)),

((1),

(ø,

a), (t)), ((z),

(c,

Â)'

(2))}

Using the notiou of

XS-s

define

thé

operations

in the

la

the

language

will be

described

associatãd.

io the

language

wil both,

syntactic

result of the pro

in

the form of

fr (or

realisations) sets.

An operatiori described by

al

element o.

= )p will

be clefined. as follows :

I"t X :-ilrir=r"t" -o iu^ny of sets,

inclexed

by the index In of

the

, i\, i e I. will be

called

a set of the type i' If

l),'then

o

l- (ir, iz, .. ', i,), t:

(sr, sz,

''',

s¿,S,r-rr

í, ..., n, i' å r",

ro

= s; ii:1,2, ..,, n, *+1,

necl

by

o

in X :

{Xr}r=¡}

is

definecl as

a

-composl-

:

:"#

;

î ffi '"j'""":ili ii*if'ïå

that is, the

corresPond'ing algo-

ï1'äff:ä"Xïu,iåI ffläti*

Given a gfammaÍ

G

anð,

)n the

ES-scheme associated

to G, a family

oi."tr itá"*.? ¡y io, X: {Xi,.r" together with all

operations supplied associatecl

to G and will be

denoted

:T

t i, f, 1"''$,?

XT

ïI",

ut

(11

set

of

a1l strings

of the

language.

Then we

have :

17 SOME OBSERVATIONS 195

(i).

So

=

L(G) being considered as individual constants

of

XS(G, L(GÐ.

(ii). r,et now be

u)1,

ru2, .., u, = L(G) of the types it, ir, ...,

in

and

o e 2i,,i > l. fi o: (o,s, t)

and

iÎ o: (ir, ir, ..., i")

then we can write o(zør,

Uu ...,wu):

sP)Lszl!)z...Snlunsn¡1or using

the

operation name a¡,¿,...iriis.u)Lszlpz,,.s;t*s,rl

r. Of

courser

o(ar, wr,...,rnr)

bclongs

to

the language and has

the type r', where t: (i). Norv,

because ¿u(C)

:

S0

and becatrse L¡(G)

-

L¿.r(G),

i:0, 1, .,., n, L,,(G):

L(C), '"r'e can for-

mulate the following

theorem:

THEoREM

2. For

eacl¿,

i, 0 < i < n

the language Ln(G) 'is ø

free ),S'

al,gebrø

of uords,

generated.

by

Lo(G) U

¿r(G) u .., u L,,r(G), uitk

the

oþerator scheme

)r" : Ü t¡

j:0 ancl

uil,t

be clenoted by

L,(G)

:

'S(¿,(C),

>dJ.

Iu this

way

the free )

-algebra

of

words suppliedby

Gin

Z(G)canbe

rvritten

as

the

pair

>s(G,

¿(G))

: >s(¿(G),

)n)

This result

lvas obtained

by

consid.eringonly operations of

then-aily 0, 1,

and

2, that is by

reducing

the

grammar

to

a Chomsky not'mal form

in

the paper

nus

[6].

From the above theorem

it

followst hat we have on one side the overlap-

ping of the

language and

on the othei

side

the )S-structure

definedon each

level of the

language.

Also,

theorem

2

show us

the relation

between levels from

the

generation and structure

point

of view.

We can define now

the

sernantic dornain

of a

given language

in

the

following rvay: let 1:

{X¿}rcr"

be a given family of

sets indexed. by

the index

,In

of the

grammar. XS-algebra (when

is defined) >S(X,

G)

:- : (X: {X,},-tn,

Xo)

is

called

an

element

of the semantic

clomain ot

I(G).

Because

the

XS-algebra

of the

language

Z(G) is

>S(¿(G). G)

:

:

(¿(G),

)"), it

is

similar to )S(X,

G),

we can

define

an

homomorphism

H:

L(G)

--t :S1X, G), called

semantic homomorphism

in the

lollowing

way:

(i). First

we define

Il on the

structure associated, to.ä-o(G),

I'hich

is

generally a finite set (or

denurrerable set).

For that let w e

Zo(G) þe án element of

the

type

i-€

1c.

'lhen H(w) wlll

be the injection oI

a in

the set

X,

which has the same

type

as ø.

(ii). r-,"t us stlppose that

H

was defined on the leve1s Lr(G), L'(G),...,Lr(G),

Fol

extenison

of H to L¡¡t(G)

we proceed

as follows: If u =

Ln+t(G),

because Zo(G)

u

Lt(G)

u ... a

Li(G) is

the set of

generators

for

l¡11(G)

there exist the, strings

'te,, u)2,

...,

wn

forro [J L¡(G) arñ' o e

X1,+r)c j :t)

\

I

()

(10)

196

so

that o(ur, u,

we

have

TEODOR RUS 18

, Ur)

:

w,

or

11)

:

(ni,i,..

,iti:

s\IÙLszI|)z , '

'

SrP)nSn*1. Then

19 SolvfE OBSERVATIONS 797

(iv). There exists an operation o €

O,(1",),

o: I[,

--> 16, denoted by o(00, 0,), rvlrere n.

-

p(nr,

nr, ..., nu) and 1[,

belongs

to the

codornai¡

of

0d.

(v). Thefollowing diagram of operation composition

ino(Iç,)

commtltes

H(*) :

(ùi,i,...i,¡i: srlf(ør)s, II (wr)

.'

. u,,H(un)s,,

¡t

In this

way

the

semantic homomorphism defined on

the first

level of the languag"

will

be homomorphic extend.

to all the

language. !h_e homo- morphilm i¿

is itr fact

an interpretatio_n of

the

language irr

the

XS-al.gebra defiåed.

by

G

in the family of

sets

y: {x¿}¡-r". This interpretation

is given

by

a constructive method and describealso the role which state rvords have,

The set

of all

)S-algebras defined

by

a given grammar G

will

be called semantic domain

of the

langtlage genelated.

by

G.

It is

cluite clear

that

a

language

has a family of

semantics,

but

each eleme.nt

of this

famil1' has a-str-ucture

similar to that of

language, becanse

it is

defined

by

the same

grammaï. It should be interesting to .*t.4y

the, classes

of

lan- guagesäefined. by some iclentity relations defined

in

XS-algebras,

We

shoulcl

o¡tain in this

way the varieties of

the

languages.

I,etnow@bea set so that @n N:Ø

and.

a function ã:@-'

--)

O(N) lvhere g(N)

denotes

the

operation scheme

as

above.

In

this

\4/ay we have defined

on the set

O(Iç,) o1 operatioris

on

16,

a

X-algebr.a Because

)6, is a

subset o1. O(Iç,)

the restriction of this structure to

the set

of

operations defined

by 2", will be

called

a

X-structure

on

X6, and

will be

d.enoted.

by 2",:

(.0,

Nc,). The effect of

some operations S

e )6, is

described

in the following rvay: let A : {A,lr-r",,

be

af.amil.y of sets indexed

by

15,,

and 0 e

@. ø0

is an

operation

in

g(N).

Let this

operation be ø 0 :

- N. Then the opetatioir supplied bl)

O

in A : {Ar}¡-¡", is

described

by the

diagram

(tlil^Al^

*,41,) ^ (/\,l,Ar:

"

.r,4,i,) x -..x(,t;..t¡ :.,,1,¡..

ør,l 't .,c,)zi "t ø.,,. '',t

I

A¡ x A¿iz x'.\

,4ô"

I¡ig. 7)

I;,

O,l

[,t X

t^," -

;"',' --- lÌl-,*- ¡ ;

I

a(.9.i,ۓr)

-4--. t!J Ftg. C

3.3, Relal.ions between languages

In the last part of the

papef we

shall

define

the relation of

transla-

tiirn

bet.r,r,een

tri,o

languagei. -Ftor

that let two

grammars

G

and

G'

be

given a L(G')

generatecl respectively

by

G

ãnd G'.

are context-free

and that

operator

schemes

we

shall

def

For

that

.l

we '

as

lN COHN

: (o', s', t'),o' e

I'å,,

s' e

Sc,,

t' € Ic. I,et N

be

the

set

of all

-n-aryties

of

òperatioás

from

O(1",)), As rve li¿ivõ obser'ed. O(^16,) can be indexed

by the set N,

O(Ic,)

:

{O,1t",)},¡=n, ând

if Ic, is not empty then N is

not

empty

too.

A function

p : liÀ

+ N rviil

be called

an

operation scheme on O(16')

if the following

conditions holcl:

(i). For

each (nr, Ø2,

...,

7¿É)

e Il which

beloilgs

to the

domain

of p'ihere

exists

iî-O(I;') the

oþeratiars o1, o2,

.. ',

oh

of the

n-aryties

71L,'lL2' .,,' iln.

(ii). there

exists a

function

0o:

I'|ixI';:x ... x Iþ

->

I[, whete

?i

: : þ(nt, nr, ...,

no).

(iii). Thcre exists

an operation

0, e

OoU",)

so that the

composition 0,(or,

or,

. .

.,

or)

is

defined

in

0(16').

tc

:

,r ,l¿,!, ) ,JA ,Ak æu)

/l .

llL

The process which

is

described

bl, this

diagram

is

as follows :

(i).

Theoperations 01, o2,

...,

on defined

by X", on the family A : :

{A¡)¡=¡a,

are

determinad

by

øl.ar, aotr,

..., eda,'To these

operations

are

corresponding

in )c, the

operation qto

:

O(00,

0,)

where

0, and

0, are described

by the

diagram

of

operation composition.

(ii). The

domain

of

aco (a<o., a<or,

.,., do¡)

where ø.c0, is given by the operation

0,, is

given

by the

coclornain

of

0n, and

the

codomain

of

ao, (øo1, ac,lr,

...,

ao¿)

is given by the

codomain

of

0,,

(iii). The

effective construction

of the result is

made

by a

special composition

of

aa1, acù2, . .

.,

o.6h indicated

by

øo,.

In this

composition sometimcs

we must

use

a state

word.

which is

deterrnined

by the

state words

of

given operations from the cornposition,

Referințe

DOCUMENTE SIMILARE

Abstract: The Canadian Immigration and Refugee Protection Act provides that one of the objectives of immigration is “to see that families are reunited in Canada.” The Act

, Convergence of the family of the deformed Euler-Halley iterations under the H¨ older condition of the second derivative, Journal of Computational and Applied Mathematics,

Keywords: trickster discourse, meaning, blasphemy, social change, transgression of social norms.. The Myth of the trickster and its

The article is a short presentation of the ROMTEXT project, a dated and annotated corpus of selected texts from the bibliography of the Dictionary of the Romanian Language, from

In the paper, by virtue of the H¨ older integral inequality, the authors derive some inequalities of the Tur´ an type for confluent hypergeometric functions of the second kind, for

We then go on to examine a number of prototype techniques proposed for engineering agent systems, including methodologies for agent-oriented analysis and design, formal

The best performance, considering both the train and test results, was achieved by using GLRLM features for directions {45 ◦ , 90 ◦ , 135 ◦ }, GA feature selection with DT and

Haskell is a general purpose, purely functional programming language exhibiting many of the recent innovations in functional (as well as other) programming language re-