Рекурсивные схемы и проблемы трансляции (Темы на автомат)

Рекурсивные схемы и проблемытрансляцииВыполнила студентка группы17133Киселёва ЮлияПример рекурсивно определяемой функции:FACT: N → ( > 0)1, если x=0,FACT (x) = x* FACT (x-1), если x>0• Рекурсивная функция задаётся с помощьюрекурсивных определений, которые позволяютсвязать искомое значение функции для заданныхаргументов с известными значениями той жефункции при некоторых других аргументах.• Рекурсивная программа - это совокупностьрекурсивных определений, задающихрекурсивную функцию, для которой аргументамислужат начальные данные программы.• Рекурсивная программа может завершиться законечное число шагов с результатом, равнымзначению запрограммированной функции длязаданных аргументов (начальных значенийпеременных), но может и продолжатьсябесконечно - тогда значение функции неопределено.{Программированиесхема программы S1и в рекурсивномначаловвод (x);FACT (a)y := a;FACT (x) =l: если p(x) то на l1; если x=0 то 1y : = g(x, y);иначе x* FACT (x-1)x : = h(x);Где a - целоена l;неотрицательное числоl1: вывод (y)Конецв операторном языкеначало целые x,y;ввод (x);y := 1;l: если x= 0 то на l1;y : = x * y;x : = x - 1;на l;l1: вывод (y)КонецВыполнение программы для a =4 :FACT (4) = если 4=0 то 1 иначе 4*FACT (4-1)=4*FACT (3)== 4* (если 3=0 то 1 иначе 3*FACT (3-1)) = 4*3*FACT (2) == 12* (если 2=0 то 1 иначе 2*FACT (2-1)) = 12*2*FACT (1) == 24* (если 1=0 то 1 иначе 1*FACT (1-1)) = 24*1*FACT (0) == 24* (если 0=0 то 1 иначе 0*FACT (0-1)) = 24Выполнение программы для a=b=1:РекурсивнаяпрограммаA (1,1) =если 1=0 то 1+1 иначе B (1,1) = B (1,1) == если 1=0 то A (0, 1) иначе C (1,1) = C (1,1) ==A (0, A(1,0)) =A(0, (если 1=0 то 1 иначе B (1,0))) =2S0 Вычисляющая значения функции Аккермана A: → A (a,b) - главный вызовA (x,y) = если x=0 то y+1 иначе B(x,y),B (x,y) = если y=0 то A(x-1, 1) иначе C(x,y),C (x,y) = A(x-1, A(x, y-1)).3 определения функций.Взаимная рекурсия - рекурсия, при которой каждая изфункций A,B,C косвенно определена через саму себя.=A(0,B(1,0)) = A(0, (если 0=0 то A (0,1) иначе C (1,0))) ==A(0,A(0,1)) =A(0, (если 0=0 то 2 иначе B (0,1))) ==A (0,2) = если 0=0 то 2+1 иначе B (0,2) = 3функциональное выражение содержит нескольковхождений символовопределяемых функций (А (0, А (1, 0)) ).Правило подстановки в этом случае требует,чтобы замещалось левое из самых внутреннихвхождений (в случае упомянутого терма —вхождение А (1,0)).Рекурсивные схемыРекурсивной схемой называется пара (τ, М), где τ —терм, называемый главным термом схемы (или еевходом), а М — такое множество рекурсивных уравнений,что все определяемые функциональные символы влевых частях уравнений различны и всякийопределяемый символ, встречающийся в правой частинекоторого уравнения или в главном терме схемы, входитв левую часть некоторого уравнения.Другими словами, в рекурсивной схеме имеетсяопределение всякой вызываемой в ней функции, причемровно одно.Стандартные схемыСхема программы - абстракция императивнойпрограммы, в которой базовые операции замененыабстрактными символами.

Интерпретация = смыслбазовых операций + значения входных данных.Программа = схема программы + интерпретация.Императивная программа содержит прямые указания, чтодолжен сделать компьютер и в каком порядке должнывыполняться инструкции.-Размеченный граф (некоторым элементам которого( вершинам, дугам ) сопоставлены числа) без свободныхдуг (все дуги-внутренние) с вершинами 5 видовvстарт – существует и единственнаvстартстарт(...)…x := t…p…стоп(...)10…петляНаправленный граф – тройка G=(V,E,Ф), где V- множествовершин, Е– множество дуг, а Ф – функция из Е в ∪ 2 , ω ∉.Дуга внутренняя, если Ф = 1 , 2 для 1 , 2 ∈ .Рекурсивные схемыСтандартные схемыПолный базисвключает четыре счетных множества символов:• X = {x1,x2,…, y1,y2,…} – переменные• F = {f,g,h,….} – функциональные символы• P={p,q,…} – предикатные символы• X = {x1,x2,…, y1,y2,…} – переменные• {если, то, иначе, (, ), , ,} – специальные символы• C = {a,b,c,…} – константы• Множество логических выражений• F = {f,g,h,….} – функциональные символы• Множество термов• P={p,q,…} – предикатные символы• Множество функциональных символов разбито на два• {старт, стоп, петля, (, ), ,, := } –непересекающихся подмножества:специальные символы(1)- множество базовых функциональных символов (f ,•Местностьсимвола:r:F∪P→N(2)g )- множество определяемых функциональных символов(F(1),G(2),Н(1))В базисе рекурсивных схем нет множества операторов,вместо него — множество логических выражений имножество термов.Логическое выражение - слово вида p(n)(1 , … , ) ,гдеp(n)- предикатный символ, а 1 , … , - термы.Рекурсивные схемыСтандартные схемыТермы слова, построенные из переменных, функциональных и специальных символов поопределенным правиламПростые термы:Условные термы:слово видаесли p то 1 иначе ,где p — логическоевыражение, 1 , —простые термы,называемые левой исоответственноправойальтернативойВызовы:термы видаF(n)(1 , … , ), где1 , … , — простыетермы, а F(n) —определяемыйфункциональныйсимволПримеры термов:Бесскобочная форма:Базовые: f (x,g (x,y)) ; h (h(a))если р(х, у) то h (h (а))Простые: f (F(x), g(x,F(y))), H(H(a)) иначе F (х)если рху то hha иначе FxВызовы: F (x), H(H(a))Базовые термы:не содержатопределяемыхфункциональныхсимволовФункциональный терм τ∈T:– x – терм, если x∈X– a – терм, если a∈C– f (τ1,…, τn) – терм, еслиf∈F, r(f)=nи τ1,…, τn – термы,– других нетПредикатные термы π:p (τ1,…, τn) – терм, еслиp∈P, r(p)=nи τ1,…, τn –функциональные термыПусть B — некоторый базис.

Расширим множество специальных символов дополнительным символом = .Рекурсивным уравнением, или определением функции F назовем слово вида: F(n)(x1 ,. . ., xn) = τ(x1 ,. . ., xn).где F(n) — n-мeстный определяемый функциональный символ; τ(x1 ,. . ., xn) — терм, содержащий переменные измножества переменных {x1 ,. . ., xn}, называемых формальными параметрами (ФРП) функции F, и никаких другихпеременных.Рекурсивная схема: пара (τ, М).Рекурсивная программа: (S, I)Примеры рекурсивных схем:S3: F(x),S2: F(x),F(x) = если p(x) то a иначе g(x, F(h(x))) F(x) = если p(x) то xA (x,y) = если p(x) то f(y) иначе B(x,y),иначе f(F(g(x)), F(h(x)))B (x,y) = если p(y) то A(g(x),a) иначе C(x,y),S0: A(x,y),C (x,y) = A(g(x), A(x, g(y)).Интерпретация• Область интерпретации D• Интерпретация I:• I:X→DI : F→ (Dn → D)I : P(n) → (Dn → {0,1})где– F(n) и P(n) – множества базовых функциональных и предикатных символов местности n, соотв.– I(f) всюду определена для любого fОпределяемые функциональные символы не интерпретируютсяСвободная интерпретация• Область интерпретации – T (множество функциональных термов)Ih(x) = ‘x’Ih(f)(τ1,…,τn) = ‘f(’ + τ1 + ‘,’ + … + ‘,’ + τn + ‘)’Ih(p) – свободно• Любые две свободные интерпретации отличаются только тем, как они определяют предикатные символы.Значение термаПусть — терм, I — некоторая интерпретация, W — некоторое состояние памяти, т.

е. совокупность значений всехпеременных, входящих в терм (или в схему, содержащую этот терм).Значение (W) терма при интерпретации I и состоянии памяти W определяется следующим образом:1) если — базовый терм, то (W) — значение этого терма, определенное так:если =x, где x- переменная, то (W) =W (x),2) если — терм вида F(n)(1 , … , ), то (W) = I(f(n))(1 A(W),2 A(W), ..., A(W)),3) если — терм вида f(n) (1 , … , ) и хотя бы один из термов 1 , … , содержит определяемый функциональныйсимвол, то (W) = I(f(n))(1 A(W),2 A(W), ..., A(W)),4) если т — условный терм вида если p(n)(1 , … , ) то иначе , то A(W), если I(p)(1 A(W),2A(W), ..., A(W)) = 1 (W)=ቊ.

A(W) − иначеЗначения термов — это выражения, содержащие элементы из области интерпретации, определяемые функциональныесимволы и символы конкретных функций.Протокол выполнения рекурсивной программы (S,I) - это конечная или бесконечная последовательностьконфигураций 1 , 2 , … такая, что:1. 1 = 1 A(0 ), где 1 — главный терм схемы S, 0 - начальное значение памяти, т.е.

всех переменных схемы S,2. i+1 получается из i заменой в i самого левого, самого внутреннего вхождения вызова F(n)(1 , … , ) (где F(n) некоторый определяемый символ,1 , … , из 1 ) на значение терма в правой части уравнения F(n)(1 , … , )= (1 , … , ) при интерпретации I и значениях переменных: (1 ) = 1 , …, ( ) = ,3. если i не содержит определяемых функциональных символов, то i - последняя конфигурация протокола.Если протокол конечен, то программа (S, I) останавливаетсяи последняя конфигурация в протоколе, если онапредставляет собой элемент из области интерпретации,считается результатом программы.

Если же последняяконфигурация — выражение, составленное из символовфункций и значений переменных, то осуществляетсявычисление этого выражения, в результат вычисления(элемент из области интерпретации) объявляетсярезультатом программы.Программа (S, I) зацикливается, если протокол бесконечен.Интерпретация I:D - множество всех целых неотрицательных чисел,I (x) = 4; I (y) = 0; I (a) = 1;I (g) = G, где G: 2 → – ф-я умножения чисел т.е.