Сборник научных трудов под редакцией доктора физико-математических наук А. Н. Горбаня красноярск кгту


Понятие кинетической машины Кирдина



страница5/32
Дата09.08.2018
Размер2.19 Mb.
#43456
ТипСборник
1   2   3   4   5   6   7   8   9   ...   32

2. Понятие кинетической машины Кирдина

Пусть Lалфавит символов. L* – множество всех конечных слов или цепочек в алфавите L. Обрабатываемой единицей является ансамбль слов M из алфавита L, который отождествляется с функцией FM с конечным носителем на L*, принимающей неотрицательные целые значения – FM: L* N {0}. Значение FM(s) интерпретируется как число экземпляров слова s в ансамбле M.

Обработка состоит в совокупности элементарных событий, которые происходят недетерминированно и параллельно. Элементарное событие S: MM’ состоит в том, что из ансамбля M изымается ансамбль K (это возможно, если для всех s ) и добавляется ансамбль K+ , т.е.. Ансамбли K и K+ однозначно задаются правилами или командами, которые объединяются в программу. Команды могут быть только трех видов:

Пусть u, w, v, f, g, k, q, s – терминальные символы, обозначающие некоторые цепочки символов из L, являющиеся подцепочками слов из L*.


1. Распад. uvw uf + gw

где u, w – произвольные, v, f, g – фиксированы. Распад однозначно задается тройкой цепочек (v, f, g) . Обозначим P1 множество таких троек.

При применении этой команды функция FM изменит свои значения следующим образом:

FM’(uvw) = FM(uvw)–1 ,

FM’(uf) = FM(uf)+1 ,

FM’(gw) = FM(gw)+1.

Команда распада применима, если FM(uvw) > 0.


2. Синтез. uk + qw usw

u, w – произвольные, k, q, s – фиксированы. Синтез однозначно задается тройкой цепочек (k, q, s) .Обозначим P2 множество таких троек.

При применении этой команды функция FM изменит свои значения следующим образом:



FM’(uk) = FM(uk)–1 ,

FM’(qw) = FM(qw)–1 ,

FM’(usw) = FM(usw)+1.

Команда синтеза применима, если FM(uk) > 0, FM(qw) > 0.


3. Прямая замена. uvw usw

u, w – произвольные, v, s – фиксированы. Прямая замена однозначно задается парой цепочек (v, s) . Обозначим P3 множество таких пар.

При применении этой команды функция FM изменит свои значения следующим образом:



FM’(uvw) = FM(uvw)–1 ,

FM’(usw) = FM(usw)+1.

Команда прямой замены применима, если FM(uvw) > 0.

Программа P применима к ансамблю M, если хотя бы одна его команда применима к M. Программа P однозначно определяется множествами P1, P2 и P3 .

Таким образом, элементарное событие S однозначно определяется правилом p, содержащимся в списке команд программы P, и ансамблем K, определяемым этим правилом, таким, что FK(s)FM(s) для любого s. Допустимое элементарное событие S для ансамбля M и программы P – это такое, для которого существует правило p, содержащeeся в списке команд программы P, и значения функции FM для слов, стоящих в левой части этого правила, положительны.

Скажем, что N допустимых событий совместны, если , где – изымаемый ансамбль для i-го события.

Ансамбль M является финальным для данной программы P, если никакая команда программы к нему не применима.

Программа P называется финитной для данного ансамбля M, если, применяя к нему команды программы в любом порядке, пока это возможно, мы обязательно получим некоторый финальный ансамбль.

Программа P является детерминированной для ансамбля M, если все финальные ансамбли совпадают.

Ансамбль M будем называть «райским садом» для программы P, если он не может быть получен ни из одного ансамбля применением программы P.

Неформально кинетическую машину Кирдина можно описать следующим образом. У нас есть банка, в которой плавают слова. Мы добавляем в эту банку правила-катализаторы, одни из них, сталкиваясь со словами, способствуют их распаду, другие, встречая пару подходящих слов, способствуют их синтезу, а третьи заменяют в словах некоторые подцепочки (рис.1).





Каталог: Library
Library -> Аппендицит
Library -> Методические рекомендации для доаудиторной подготовки к практическим занятиям по инфекционным болезням
Library -> Нормы сроков службы стартерных свинцово-кислотных аккумуляторных батарей автотранспортных средств и автопогрузчиков
Library -> Что дает страхование ответственности перевозчика
Library -> Сообщения информационных агентств
Library -> Закон республики таджикистан о документах, удостоверяющих личность


Поделитесь с Вашими друзьями:
1   2   3   4   5   6   7   8   9   ...   32




База данных защищена авторским правом ©vossta.ru 2022
обратиться к администрации

    Главная страница