[̲] [] [] [ ]

 

7.8.

 

. , , ', ': , . , W (. .5.8).

- . AC :

         L AC;

         Î , X Î AC, Xa Î AC - , X.

³, ChC=W - Ch.

AC , , W .

:

1) '

 

_ + _: AC, AC -> AC;

 

2)

 

add(_, _): A, AC -> AC;

 

3)

 

hd(_): AC -> A;

 

4)

 

tl(_): AC -> AC;

 

5)

 

app(_, _): AC, A -> AC;

 

6)

 

lst(_): AC -> A;

 

7)

 

bgn(_): AC -> AC;

 

8)

 

len(_): AC -> ;

 

9)

 

_ = _: AC, AC -> ;

 

.

 

7.8.1

 

t - ; Dt - ; ^ - , Dt. , t, tf

 

----------------------

tf = t;

L---------------------

 

Dtf, (A,^,B): ,

 

Dtf = {(,^,): , Î DtC}.

 

(A,^,B) A^B. , F=^, (lt(F)), - (rt(F)). + (ct(F)).

 

A B

---------------- ^ ----------------

F b . .. c q . .. r

L---+---+-----+---- L---+---+-----+----

<----- lt(F) ---> <----- rt(F) --->

 

File(t) . , lt, rt ct : , . (, ).

F - t, - t.

 

1. ³:

- (End of File)

 

eof(_): t ->

 

eof(F) = (rt(F)=L). eof :

 

---------------- ^

F b . .. r L

L---+---+-----+----

<----- lt(F) --->

 

, ct(F)=lt(F)=, rt(F)= L.

 

2. - :

 

- ( )

 

{ ct(F)= }

 

(F)

 

{ lt(F)= L & rt(F)=ct(F)= };

 

 

B

^ ----------------

F L b . .. r

L---+---+-----+----

<----- rt(F) --->

 

-

 

{ }

 

(F)

 

{ lt(F)=rt(F)=ct(F)= L };

 

F L ^ L

 

- F

 

A B

---------------- ^ ---------------- -- --

F b . .. c q . .. r

L---+---+-----+---- L---+---+-----+---- L------

<----- lt(F) ---> <----- rt(F) --->

 

 

{ lt(F)= & rt(F)= & ct(F)=+ & Øeof(F) }

 

(F, )

 

{ lt(F)=app(,hd()) & rt(F)=tl() & ct(F)=+ };

 

A B

------------------- ^ ------------- -- --

F b . .. c q . .. r

L---+---+-----+---+---- L---+-----+---- L------

<------ lt(F) ------> <-- rt(F) -->

 

- F

 

---------------- ^ -- --

F b . .. r L s

L---+---+-----+---- L------

<---- lt(F) ---->

 

{ lt(F)= & eof(F) }

 

(F, )

 

{ lt(F)=app(,) & eof(F) }

 

------------------- ^ -- --

F b . .. r s L s

L---+---+-----+---+---- L------

<------ lt(F) ------>

 

-

 

{ F = A^ }

 

(F)

 

{ ct(F)=A+ };

 

. , , , , .

.

, , -. - , , - .

 

7.13. ,

 

n n-1

() = + +. .. + + , <> 0,

n 0 1 n-1 n 0

 

, .

 

PF ( : [0..N] ;

F: )

I: ;

(F);

I<-0 N

(F, [I])

.

 

. , , , .

,

 

t =

: t; (7.6)

s: q

;

 

t - .

 

7.14. ' ct() = ct(F)+ct(G).

 

Union ( F, G, : t)

X: t;

(F); (G); ();

Øeof(F)

(F, X); (, X)

;

Øeof(G)

(G, X); (, X)

;

(F);(G); (H)

.

 

F G, , ct(F)+ = ct(G).

 

7.15. .

 

BeginF ( Q: ; F, G: t)

X, Y: t;

(F); (G);

Q <- ;

Øeof(F) & Q

Q <- Øeof(G);

Q

(F, X); (G, Y);

Q <- X=Y

;

(F);(G)

.

 

7.16. .

 

SearchF ( K: t;

F: t;

: ; Y: q)

X: t;

(F); <- ;

Ø(eof(F) V )

(F, X);

<- X.=K;

;

Y <- X.s ;

(F)

.

 

7.8.2

 

, . .

t - ; Dt - ; ^ - , Dt. , t, td

 

---------------------------

td = t;

L--------------------------

 

.

 

Dtd = {(,^,): , Î DtC}.

 

³ eof , , , , .

2 :

 

a) ( )

 

---------------- ^ -- --

F b . .. r L s

L---+---+-----+---- L------

<---- lt(F) ---->

 

{ lt(F)= & eof(F) }

 

(F, )

 

{ lt(F)=app(,) & eof(F) }

 

------------------- ^ -- --

F b . .. r s L s

L---+---+-----+---+---- L------

<------ lt(F) ------>

 

b)

 

A B

---------------- ^ ---------------- -- --

F b . .. c q . .. r s

L---+---+-----+---- L---+---+-----+---- L------

<----- lt(F) ---> <----- rt(F) --->

 

{ lt(F)= & rt(F) = B & Øeof(F) }

 

(F, )

 

{ lt(F)=app(,s) & rt(F)=tl(B) & Øeof(F) }

 

A B

------------------- ^ ------------- -- --

F b . .. c s q . .. r s

L---+---+-----+---+---- L---+-----+---- L------

<------ lt(F) ------> <-- rt(F) -->

 

:

 

1. :

- ( )

 

(_): t ->

 

- ( , , 0)

 

(_): t ->

 

0 1 ... i-1 i

---------------- ^ ----------------

F b . .. c q . .. r

L---+---+-----+---- L---+---+-----+----

<----- lt(F) ---> <----- rt(F) --->

 

2. :

-

 

0 A i-1 i B

-------------------------- ^ -------------

F b . .. c d . .. e q . .. r

L---+---+-----+---+---+-----+---- L---+-----+----

<----------- lt(F) -----------> <-- rt(F) -->

 

{ lt(F)= & rt(F) = B & ct(F) = A+B }

 

(F, i)

 

{ len(lt(F))=i & ct(F) = A+B }

 

0 i-1 i

--------------- ^ ------------------------

F b . .. c d . .. e q . .. r

L---+---+-----+---- L---+-----+---+---+-----+----

<---- lt(F) ----> <--------- rt(F) --------->

 

(F, i) i>(F).

 

7.17. K Y ( t (7.6)).

 

ReplaceF ( K: t; Y: q;

F: t)

X: t; I: ;

(F);

I <- 0 (F)-1

(F,X);

X.=K

(F,I); (F,Y)

;

(F)

.

 

, , .

 

 

7.8.3

 

. , . , () . #. ,

 

Dtxt = {(,^,): , Î ChC}.

 

:

 

F: ;

 

³ eof , , , .

:

 

1. ³:

-

 

eoln(_): t ->

 

eoln(F) = (hd(rt(F))=#). eoln :

 

A B

---------------- ^ ----------------

F b . .. c # q . .. r

L---+---+-----+---- L---+---+-----+----

<----- lt(F) ---> <----- rt(F) --->

 

2. :

- (F,x), x .

 

a)x -

 

A B

---------------- ^ -------T------------ -- --

F b . .. c q # . .. r

L---+---+-----+---- L---+---+---+-----+---- L------

<----- lt(F) ---> <------- rt(F) ----->

 

{ lt(F)= & rt(F) = B & Øeof(F) }

 

(F, )

 

{ lt(F)=app(,hd(B)) & rt(F)=tl(B) & x=hd(B) }

 

A B

------------------- ^ ----T------------ -- --

F b . .. c p q # . .. r p

L---+---+-----+---+---- L---+---+-----+---- L------

<------ lt(F) ------> <---- rt(F) ---->

 

b)x -

 

A B

---------------- ^ -------T------------ -- --

F b . .. c q # . .. r

L---+---+-----+---- L---+---+---+-----+---- L------

<----- lt(F) ---> <------- rt(F) ----->

 

{ lt(F)= & rt(F) = B & Øeof(F) & B = C+#+D }

 

(F, )

 

{ lt(F)=+C & rt(F)=#+D & x=C }

 

A B

------------------T---- ^ ------------- -- ---

F b . .. c p q # . .. r pq

L---+---+-----+---+---+ - L---+-----+---- L-------

<-------- lt(F) --------> <-- rt(F) -->

 

- #(F,x), x .

 

a)x ; , .

 

A B

---------------- ^ -------T------------ -- --

F b . .. c q # . .. r

L---+---+-----+---- L---+---+---+-----+---- L------

<----- lt(F) ---> <------- rt(F) ----->

 

{ lt(F)= & rt(F) = B & Øeof(F) & B = C+#+D }

 

# (F, )

 

{ lt(F)=+C+# & rt(F)=D & x=hd(B) }

 

A B

------------------T---T--- ^ ---------- -- --

F b . .. c p q # . .. r p

L---+---+-----+---+---+---+---- L-----+---- L------

<---------- lt(F) ----------> < rt(F) >

 

b)x ; , .

 

A B

---------------- ^ -------T------------ -- --

F b . .. c q # . .. r

L---+---+-----+---- L---+---+---+-----+---- L------

<----- lt(F) ---> <------- rt(F) ----->

 

{ lt(F)= & rt(F) = B & Øeof(F) & B = C+#+D }

 

# (F, )

 

{ lt(F)=+C+# & rt(F)=D & x=C }

 

A B

------------------T---- ^ ------------- -- ---

F b . .. c p q # . .. r pq

L---+---+-----+---+---+ - L---+-----+---- L-------

<-------- lt(F) --------> <-- rt(F) -->

 

- (F,x), x .

 

a)x -

 

---------------- ^ -- --

F b . .. r L s

L---+---+-----+---- L------

<---- lt(F) ---->

 

{ lt(F)= & eof(F) }

 

(F, )

 

{ lt(F)=app(,) & eof(F) }

 

------------------- ^ -- --

F b . .. r s L s

L---+---+-----+---+---- L------

<------ lt(F) ------>

 

b)x -

 

---------------- ^ -- --

F b . .. r L st

L---+---+-----+---- L------

<---- lt(F) ---->

 

{ lt(F)= & eof(F) }

 

(F, )

 

{ lt(F)=+ & eof(F) }

 

------------------T---- ^ -- --

F b . .. r s t L st

L---+---+-----+---+---+---- L------

<-------- lt(F) -------->

 

- #(F,x), x .

 

a)x -

 

---------------- ^ -- --

F b . .. r L s

L---+---+-----+---- L------

<---- lt(F) ---->

 

{ lt(F)= & eof(F) }

 

# (F, )

 

{ lt(F)=app(app(,),#) & eof(F) }

 

------------------T---- ^ -- --

F b . .. r s # L s

L---+---+-----+---+---+---- L------

<-------- lt(F) -------->

 

b)x -

 

---------------- ^ -- --

F b . .. r L st

L---+---+-----+---- L------

<---- lt(F) ---->

 

{ lt(F)= & eof(F) }

 

# (F, )

 

{ lt(F)=++# & eof(F) }

 

------------------T---- ^ -- --

F b . .. r s t L st

L---+---+-----+---+---+---- L------

<-------- lt(F) -------->

 

, , #(F) #(F). , , , .

 

7.18. c A.

 

ReplaceText ( c: ; A: ;

F,G: )

Replace(S, A: c: ):

S1: ;

S1 <-

S <>

hd(S) = c S1 <- S1+A

S1 <- app(S1,hd(S)) ;

S <- tl(S)

;

Replace <- S1

;

S, S1: ;

(F); (G);

Øeof(F)

#(F,S);

S1 <- Replace(S,A,c);

#(G,S1)

;

(F); (G)

.

 

[̲] [] [] [ ]