Нормальные алгорифмы Маркова.

Автор - А.А. Марков, отдавал предпочтение транскрипции алгорифм. Нормальные алгорифмы Маркова

представляются нормальной схемой подстановок, которая состоит из совокупности подстановок,

расположенных в определенном порядке. Подстановки имеют вид: P ® (·)Q(P ® Q –(простая)

подстановка, P ® ·Q –заключительная подстановка).

Говорят, что строка R входит в строку L, если L имеет вид L1RL2.

Говорят, что подстановка применима к слову, если строка, соответствующая левой части подстановки,

входит в слово. Применение заключается в замене в преобразуемом слове левой строки подстановки

правой.Две особые подстановки:

P ® - аннулирующая.

® Q - порождающая.

Механизм работы нормальных алгорифмов:

Дано (преобразуемое) слово – цепочка символов фиксированного алфавита и нормальная схема

подстановок, содержащая фиксированную последовательность простых и заключительных подстановок.

1) Слово всегда просматривается слева направо.

Схема подстановок просматривается всегда начиная с первой подстановки и, если подстановку можно

применить, то она применяется к самому левому вхождению этой строки в преобразуемое слово.

2) Работа алгоритма заканчивается тогда, когда ни одна из подстановок не применима, либо.использована

заключительная подстановка.

Примеры.

Нормальная схема преобразуемое

подстановок словоМУХА

xx ® y xxxyyyzzz Х ® К МУКА

xy ® x yxyyyzzz М ® Р РУКА

yzy ® x yxyyzzz КА ® ЛОН РУЛОН

zz ®. z yxyzzz РУ ®. СЛ СЛОН

yy ® x yxzzz

yxzz

Примеры алгорифмов, использ. специальные символы, аннулирующие и порождающие подстановки:

Удвоение исходной строки Обращение исходной строки

aх ® хbхa aa ® ba

aу ® уbуa ba ® b

bхх ® хbх bх ® хb

bху ® уbх bу ® уb

bух ® хbу b ®

bуу ® уbу aху® уaх

b ® aух ® хaу

a ®. ® a

® a

Рефал

LISP, созданный в начале 60-х годов, не единственный функциональный язык, хотя и самый распростран.

Интересный функциональный язык РЕФАЛ был разработан в 70-х годах нашим соотечественником

Турчиным и исподльзовал математическую модель нормальных алгорифмов Маркова.

   
 
 
 

 


21. Язык РЕФАЛ.

k………., - конкретизирующие скобки

«~» - эквивалент «®»

«……» - текст (название программы, комментарий)

Выделение первого элемента:

k «пер» Se|~ «S»

k «пер» e ~

 

 

       
   


22. Лямбда-исчисление. ЛИСП.

l-исчисление, основоположником которого считают Алонзо Черча, фактически, и стало основой

теории алгоритмов и первой конкретизации алгоритма. l-исчисление рассматривают также как основу

таких важных разделов математики, как функциональное программирование и комбинаторная логика.

l-исчисление (нотация, способ записи) формализует понятие функции не как множества или графика, а как

правила.

В основе l-исчисления лежит операция аппликации.

Аппликация - применение функции к аргументу (можно применить только известную функцию).

Язык состоит из: l-терм:

1. Множества переменных (х1...). 1. Переменная или константа - l-терм.

2. Множества констант(с1...). 2. Если х - переменная, и М - некоторый l-терм, то lх.М тоже l-терм.

3. Символа аппликации . . 3. Если М и N l-термы, то MN тоже l-терм.

4. Символа абстракции l.

5. Символа равенства =.

Формула - любое выражение вида M=N, где M и N l-термы.

Замечание. В литературе прикладного плана нередко используется несколько иная терминология и форма

записи.

f = lx.x + x

f - название, ранее не названной функции.

l - оператор.

х - аргумент.

.-комбинатор.

х + х - выражение, задающее значение функции.

Аксиомы:

1. M = M.

2. (lx.M)N = M {N/x} b-редукция. где {N/x} – подстановка N вместо всех вхождений x в М.

[В альтернативном представлении часто используемая b-редукция записывается, например, так

(lx.f(x))(a) = f(a)]

3. lx.M = ly.M при {y/x} a-конверсия.

где {у/x} – подстановка у вместо всех вхождений x в М.

Правила вывода:

M = N; N = M. ; M = N, N = P ; M = P. ; M = N ; PM = PN. M = N; MP = NP.; M = N lx.M = lx.N.

Рассмотрим примеры b-редукции (в прикладной варианте записи)

(lх.х + 2у)(а) = а + 2у, (lу.х + 2у)(а) = х + 2а

(lх.(lу.х + 2у))(а)(b) = (lу.а + 2у)(b) = a + 2b, (lx.((ly.xy)u))( lv.v) = (ly.(lv.v)y)u = (lv.v)u

(lx.((ly.xy)u))( lv.v) = (lx.xu)(lv.v) = (lv.v)u, (lx.xx) (lx.xx) = (lx.xx) (lx.xx) = (lx.xx) (lx.xx) =…

((lx.x*3) (ly.if y > 4 then e = 2 else x/2) (ly.y>2)) (5) = 2*5 = 10

(ln.(lx.x-n))(2) = lx.x-2, (lf.2*f(8) – f(f(8)))(half) = 2*8/2 – (8/2)/2 = 6 (half – половина).

Лисп

Первым языком функционального программирования был язык LISP и многие базовые понятия этого языка

стали классикой функционального программирования.

Базовые функции функционального программирования:

car(x) - дает первый элемент списка х ;

cdr(х) - хвост списка ( список без первого элемента) ;

cons(x,y) - добавляет элемент х к списку у;

append(x,y) - добавляет список y к списку x ;

Примеры.

Пусть x = (1, 2, 3) y = (4, 5)

car(x) = (1);

cdr(х) = (2, 3);

cons(x,y) = ((1, 2, 3), 4, 5);

append(x,y) = (1, 2, 3, 4, 5).

Синтаксис LISP достаточно архаичный, поэтому воспользуемся способом записи функциональных

программ с помощью специальной нотации, ставшей популярной с легкой руки Хендерсона.

Примеры.

Функция длвычисления длины списка

Для (х) º if(x) = nil then 0 else дл(cdr(x)) + 1

Вычислим функцию для конкретного списка.

дл(A, B, C) = дл(B, C) + 1

дл(B, C) = дл(C) + 1

дл(C) = дл(nil) + 1

дл (nil) = 0

"Пройдя" в обратном направлении можно получить числовое значение.

Обращение списка обр, то есть список A, B, C обратится в список C, B, A

обр(x, y) º if x = nil then y else обр(cdr(x), cons(car(x), y))

Вычислим функцию для конкретного списка

обр(A, B, C, nil) = обр((B, C), (A))

обр((B, C), (A)) = обр((C), (B, A))

обр((C), (B, A)) = обр((nil), C, B, A)

Здесь использован популярный прием функционального программирования "сумка". Это позволяет

получить результат сразу, без обратного прохода.

   
 
 
 

 


Язык Бэкуса.

формальная система определения синтаксиса, в которой одни синтаксические категории последовательно

определяются через другие. Используется для описания контекстно-свободных формальных грамматик.

Как и в БНФ, описание грамматики в РБНФ представляет собой набор правил, определяющих отношения

между терминальными символами (терминалами) и нетерминальными символами (нетерминалами).

Терминальные символы — это минимальные элементы грамматики, не имеющие собственной

грамматической структуры. В РБНФ терминальные символы — это либо предопределённые

идентификаторы (имена, считающиеся заданными для данного описания грамматики), либо цепочки —

последовательности символов в кавычках или апострофах.

Нетерминальные символы — это элементы грамматики, имеющие собственные имена и структуру.

Каждый нетерминальный символ состоит из одного или более терминальных и/или нетерминальных

символов, сочетание которых определяется правилами грамматики. В РБНФ каждый нетерминальный

символ имеет имя, которое представляет собой строку символов.

Правила

Правило в РБНФ имеет вид:

идентификатор = выражение.

где идентификатор — имя нетерминального символа, а выражение — соответствующая правилам РБНФ

комбинация терминальных и нетерминальных символов и специальных знаков. Точка в конце —

специальный символ, указывающий на завершение правила.

Семантика правила РБНФ — нетерминальный символ, заданный идентификатором слева от знака

«равно», представляет собой определяемую выражением комбинацию терминальных и нетерминальных

символов.

Полное описание грамматики представляет собой набор правил, который последовательно определяет

все нетерминальные символы грамматики так, что каждый нетерминальный символ может быть сведён

к комбинации терминальных символов путём последовательного (рекурсивного) применения правил.

В определении РБНФ нет никаких специальных предписаний относительно порядка записи правил, хотя

такие предписания могут вводиться при использовании РБНФ программными средствами,

обеспечивающими автоматическую генерацию программ синтаксического разбора по описанию

грамматики.

(/+)(*)Т:<<1,2,3>> , <<4,5,6>>

/ - Ветовка

– операция композиции

Т – транспозиция

(/+)(*)Т: <<1,6>>, <<2,5>>, <<3,4>>

(/+):<<6,10,12>>

:28

Программа не динамична APL