Последовательности и файлы

Пусть X – произвольный алфавит (конечное множество). Рассмотрим последовательности символов из этого алфавита: x₁ x₂ … x_n (x_i  X). Пустую последовательность обозначим . Пусть:

• (X) или для краткости просто   пространство всех конечных последовательностей над X, т. е.

(X) = {x₁ x₂ … x_n: nN₀, x_i  X   i1..n},

при этом   ;

• _k(X) или для краткости просто _k  пространство конечных последовательностей длины не менее k, т. е.

_k(X) = {x₁ x₂ … x_n: n  k, nN₀, x_i  X   i1..n};

таким образом,  = ₀  ₁  ₂ ... .

Определим операцию postfix:   X   добавления Эл---та в конец последовательности, т. е. если   = x₁ x₂ … x_n, то postfix(, x) = x₁ x₂ … x_n x , а postfix(, x) = x. Иногда эту операцию удобнее записывать в инфиксной форме, используя для нее специальный знак, например «*», т. е. postfix(, x) =  * x. В этих обозначениях  * x = x₁ x₂ … x_n x и  * x = x. Если   _k, то  * x  _k + 1.

Тогда конструктивно последовательность можно определить так:

1)   есть последовательность;

2) если   последовательность, то и  * x  последовательность;

3) ничто другое (кроме пп.1 и 2) не есть последовательность.

Полезно дополнительно определить следующие операции над последовательностями:

first: ₁  X, rest: ₁  , prefix: X    ₁,

и если    и   = x₁ x₂ … x_n, то

first() = x₁, rest() = x₂ … x_n, prefix(first(), rest()) = .

Последовательный файл (или далее просто файл) из записей типа X (file of X)  это реализация математического понятия последовательности с ограниченными способами доступа к элементам. Наглядная модель файла представлена на рис. 3.1. Положение ленты относительно головки чтения-записи определяется разбиением ее (ленты) на две части: левую L(F) и пра-



L(F)





R(F)



















Лента





Головка чтения-записи

Метка конца файла

Рис. 3.1. Наглядная модель последовательного файла

вую R(F). Кроме того, файл может находиться в одном из трех режимов: неопределенном (n), чтения (r), записи (w). Таким образом, файл можно определить как упорядоченную тройку F = (L(F), R(F), St(F)), где индикатор режимов St(F)  {n, r, w}. Состояние файла R(F) =  идентифицируется предописанной функцией (предикатом) Eof(F): если R(F) = , то Eof(F) = true, иначе Eof(F) = false (рис. 3.2).

F:				
			
	Eof(F) = false

	F:				
					
		Eof(F) = true

Рис. 3.2. Действие функции Eof(F)

Определим основные операции над файлами.

1. Установка режима записи: Rewrite(F). Семантика этой операции задается свойством {true} Rewrite(F) {Eof(F) & (L(F) =  ) & (St(F) = w)}  и иллюстрируется на рис. 3.3.

F:				
				

	F:	
		

Рис. 3.3. Установка режима записи Rewrite(F): слева  состояние до

операции, справа  состояние после операции

2. Запись в файл: Write(F, x). Семантика этой операции (аналога postfix) задается свойством

{(St(F) = w) & Eof(F) & (L(F) =   )}

Write(F, x);

{(St(F) = w) & Eof(F) & (L(F)=  * x )}

и иллюстрируется на рис. 3. 4.

F:			
			
x :

	F:				
					
	x:		
		Запись

Рис. 3.4. Запись в файл Write(F, x): слева – состояние до операции,

справа – состояние после операции

3. Установка режима чтения: Reset(F). Семантика операции задается свойством {F =   } Reset(F) {(L(F) = ) & (R(F) = ) & (St(F) = r)} и иллюстрируется на рис. 3.5.

F:				
			

F:				
	

Рис. 3.5. Установка режима чтения Reset(F): слева – состояние

до операции, справа – состояние после операции

F:				
		
x:

F:				
			
x:		
	Чтение

Рис. 3.6. Чтение из файла Read(F, x): слева – состояние до операции,справа –сост. после операции

4. Чтение из файла: Read(F, x). Семантика этой операции задается свойством

{(St(F) = r) & not Eof(F) & (L(F) = ) & (R(F) = )}

Read(F, x)

{(St(F) = r) & (L(F) = *first()) & (R(F) = rest()) & (x = first())}

Билет№21 Индуктив ф-ции на пространстве послед:опред,схеаа выч,Крит индуктив №21