1610906301-73dade1bb16d31c957842031de4c898c (Краткий конспект к экзамену), страница 3

L`(a)= {a}2. L`(∅)=∅3. L`(A o B)= {L(A) o L(B)}4. L`(A+B) = {L(A)∪L(B)}(В регулярных выражениях Α+Β и А ∪ В — эквивалентные обозначения)Языки такого вида называются регулярными языками.Теорема 5.3 (о эквивалентности регулярных и автоматных языков)Язык L регулярный <=> Язык L автоматныйДоказательство:=>Докажем что для любого регулярного выражения α L`(α) — автоматный.Докажем это утверждение индукцией по длине α, рассмотрев в качестве базы одноэлементноевыражение и выражение, состоящее из пустого множества.При |α|=1, α=a L`(α)={a} распознается, например детерминированным автоматом →Ο →(a) Ο!Где Ο! - конечное состояние.При α=∅.

L`(α)=∅ и читается например →Ο!.База индукции доказана. Теперь воспользуемся вторым ее вариантом (Определение 1.2)Пусть утверждение верно для всех регулярных выражений β: |β|<|α|. Докажем для αПусть β и γ — регулярные языки: |β|<|α| ^ |γ|<|α|Если α=β* то L`(α)=L`(β*)=L`(β)* - автоматный по теореме 5.2.Если α=β ο γ, то L`(α)=L`(β ο γ)=L`(β) ο L`(γ) но так как по предположению индукции оба этихязыка автоматные то по теореме 5.2 их конкатенация тоже является автоматным языком.Если α=β+γ то L`(a)=L`(β+γ)=L`(β)∪ L`(γ) но по теореме 5.2 объединение автоматных языков —автоматный язык.Следовательно мы доказали что в каком бы виде не представлялось выражение α его язык будетавтоматным.<=Пусть L=L(), где - конечный автомат.Докажем что L() - регулярный.Пусть {1,...n} (n>=0) — множество всех состояний при этом 1 — начальное состояние.Определим R(i,j,k): i,j ∈{1...n}, k∈{0..n} как язык, состоящий из всех слов, прочитываемых изсостояния i в состояние j в котором все состояния, кроме, может быть, i, j имеют номер<=k.(содержатся в списке 1...k)Докажем следующую лемму:Лемма 5.2Все R(i,j,k) — регулярные языкиДоказательство:Докажем индукцией по k.Пусть k=0.Тогда все R — языки, прочитываемые по пути i → j без промежуточных состояний (нельзяполучить состояние под номером 0)Рассмотрим два случая: i=j, i≠j1)i≠j:Пусть между i и j нет дуги.

Тогда мы не можем прочитать ни одного слова, и R(i,j,0)=∅ регулярный язык.Пусть дуга есть:Тогда по ней можно прочитать только однобуквенное слово вида {a}, язык, состоящий только изодного слова является регулярным. Тогда заметим что R является объединением всех такиходнобуквенных слов и следовательно объединением регулярных языков т. е. Сам являетсярегулярным.2)i=j:Тогда весь R состоит из одного состояния с петлей.

Заметим что по такому R можно прочитатьтолько однобуквенные слова и пустое слово. Но, как мы уже заметили, язык состоящий изобъединения однобуквенных слов является регулярным, как и язык, состоящий из пустого слова.Следовательно их объединение=R также является регулярным.База индукции доказана.Пусть R(i,j,k) — регулярный. Докажем что R(i,j,k+1) также регулярный.Пусть некоторое слово ∈ R(i,j,k+1) => оно читается либо вдоль пути вида Οi →...→ Ο(k+1) →… → Ο(k+1) → … → Oj.

Либо вдоль пути Οi → … → Oj (по пути без единого прохода посостоянию k+1)В первом случае любое слово представимо в виде R(i,k+1,k) o R(k+1,k+1,k)* o R(k+1,j,k)Во втором представимо в виде R(i,j,k)Таким образом любое слово из R(i,j,k+1) представимо в виде: R(i,k+1,k) o R(k+1,k+1,k)* oR(k+1,j,k) ∪ R(i,j,k).Заметим что так-как мы доказываем лишь по третьему аргументу, то мы можем сказать чтоязыки R(i,k+1, k), R(k+1,k+1,k), R(k+1,j,k) по предположению индукции регулярные.Тогда заметим что R(i,j,k+1) представляется как объединение регулярных языков иследовательно сам является регулярным.Тогда из леммы 5.2 следует, что любой язык вида R(1,j,n): j∈F — регулярный (то есть языксостоящий из всех слов L, прочитываемых из начального состояния в некоторое конечное)) нотак как L=∪R(1,j,n) то L будет являться регулярным как объединение регулярных языков, что итребовалось.Тема 6:Частично рекурсивные функцииС данной темы начинается курс теории алгоритмов.

Каковы же свойства алгоритма?Их можно выделить несколько:1. Конечность описания2. Алгоритм исполняется по шагам3. Имеется результат (не для любых данных, на некоторых он может и выдать что решениянет или же застрять бесконечно вычисляя )4. Алгоритм решает конкретную задачуЦентральным в данном разделе будет понятие «Вычислимости»Формально определить его можно через, например Частично рекурсивные функции, МашиныТьюринга, RAM (Random access machines), Нормальные Алгорифмы Макрова, Мини-машины ит. д. Для начальных определений же будем пользоваться интуитивным понятием вычислимости.В качестве аргументов будем использовать натуральные числаОпределение 6.1Простейшими вычислимыми функциями называются0(x)=0,s(x)=x+1,Imn(x1,...xn)=xm, 1<=m<=n.Определение 6.2Пусть есть частичные (не обязательно определенные везде) функции f(x1...xm),g1(x1,...xn),...gm(x1,...xn)Результатом применения к ним Оператора суперпозиции (S) является f(g1(x1,...xn),…,gm(x1,...xn)) (Сначала вычисляются значениям функций g1..gm а потом функция f(g1,...gm)).Кстати говоря можно рассматривать применение этого оператора как алгоритм: сначалавычисляем значения внутри а затем подставляем.Если хотя бы одно из промежуточных значений не будет вычислено, то не будет вычислена и всяфункция (Например f(y), Где y — произв набор аргументов всегда принимает значение 1.

Ноесли один из аргументов не вычислим то мы не сможем вычислить и f(y) даже с учетом того, чтозначение нам уже известно.Определение 6.3Пусть даны частичные функции h(z,y,x`) и g(x`), x`={x1,...xm}. При применении к ним операторапримитивной рекурсии мы получим функцию f определенную следующим образом:f(0,x`)=g(x)f(y+1,x`)=h(f(y,x`),y,x`)Вычисление значения f(y,x`) получается при постепенном вычислении f(0,x`), f(1,x`)… (Инымисловами чтобы получить значение f(y,x`) мы для начала выражаем каждое значение черезпредыдущий элемент и затем вычисляем, пользуясь уже заданным базовым элементом (этоможет напомнить как рекурсию, так и индукцию: действительно, мы, зная «базу» делаем из неешаг в следующем вычислении, как рекурсию же это можно понимать через объяснение, данноевыше.)Когда x` имеет длину 0 функция вырождается вf(0)=a, a — constf(y+1)=h(f(y),y)Если одно из значений f(k,x`) не вычислимо, то и вся функция не вычислима.Определение 6.4Пусть задана функция g(z,x`) результатом применения к ней Оператора минимизации (Μ) илиже μ оператора является функция f(x`) которая задается следующим образомf(x`)=y тогда и только тогда когда (для любого i<y (g(i,x`) определена)^(g(i,x`)≠0) ) ^ (g(y,x`)=0)Вычисление происходит следующим образомif g(0,x`)=0 then f(x`)=0elseif g(1,x`)=0 then f(x`)=1…Если одна их промежуточных g(k,x`) не вычисляется, то не вычисляется и fПример:Пусть g(0,x`) не вычисляется, а g(1,x`)=0.

Программа никогда не завершит работу, посколькуможет зациклить вычисление g(0,x`) и не сможет дать точный ответ на то, минимум это или нет.Обозначение: f(x`)=μ(y,g(y,x`)=0)ЗамечаниеПрименением этого оператора можно получить не всюду определенную функцию.Например пусть g(y,x`)=s(x)f(x`)=(μy(g(y,x`))=0), но g(y,x`) не может быть равно 0, при натуральных значениях аргумента.Определение 6.5Функция f:N^k → N называется частично рекурсивной, если существует последовательностьфункций f1...fn=f такая что каждая fi либо простейшая либо получается с помощью одного изоператоров S,R,M из функций с меньшими номерами.

(Если в этом определении заменить S,R,Mна S,R то мы получим определение примитивной рекурсивной функции) Примитивнорекурсивные функции всюдуопределены (S и R сохраняют всюду определенность).Лемма 6.1Следующие функции примитивно рекурсивны:1)f(x)=a, a constДоказательство:f(xn)=s(s(s...(s(0(x))…) (а раз)2)f(x,y)=f(x+y)Доказательство:Заметим что x+0=x, x+(y+1)=(x+y)+1Тогда можно использовать оператор примитивной рекурсии и записать в следующем видеf(x,0)=I(1,1)(x)f(x,y+1)=s(x+y)=s(f(x,y))Таким образом мы получили реккурентную формулу выражения суммы через простейшиефункции.3)f(x,y)=x*yДоказательство:x*0=0, x*(y+1)=xy+x.Тогда вновь используем оператор R и запишемx*0=0(x)x(y+1)=x*y+x=f(x,y)+I(1,1)(x) (суперпозиция f(x,y) и Ι(1,1)(x))Зададим ее: h(z,y,x)=z+xf(x,0)=0(x)f(x,y+1)=h((f(x,y),y,x)4)x^y, где 0^0=1Доказательство:x^0=1=s(0(x))x^y+1=(x^y)*x (но так как умножение— примитивно рекурс., то мы получили требуемоевыражение)5)sgn(x)Доказательство:sgn(0)=0(x)sng(x+1)=s(0(x))6)!sgn(x) (обратный сигнум)sgn(0)=s(0(x))sgn(x+1)=0(x+1)o7)x- 1= 0, если x=0; x-1 если x>0.o0- 1=0oy+1- 1=y=I(1,1)(y)o8)x- y=x-y, x>=y; 0 если x<yox- 0=x=I(1,1)(x)oo ox- (y+1)=(x- y)- 1oo8)|x-y|=(x- y)+(y- x)Определение 6.6Пусть R⊊N^k — отношение.Тогда его характеристической функцией называется функция χR имеющая вид χR(x`)=1, еслиx`∈R; 0 если x`∉R.УтверждениеR называется вычислимым отношением, если χR — о.р.ф (общерекурсивная функция — всюдуопределенная ч.р.ф)Предложение 6.1Пусть R(y1,...yk) — вычислимое отношение, а f1(x`),..,fk(x`) - о.р.ф Тогда отношение R`={x`|f1(x`),...fk(x`)∈R} вычислимоеДоказательство:Достаточно проверить что всегда выполняется равенство χR`(x`)=χR(f1(x`),...fk(x`))Предположим что χR(x`)=1Но тогда f1(x`)...fk(x`)∈R и χR`(f1(x`)...fk(x`))=1Тогда предположим что χR(x`)=0Но тогда аналогично χR`(f1(x`)...fk(x`))=0Таким образом характеристическая функция R` вычислима, а следовательно и само отношениевычислимо.Элементы математической логикиЗдесь набирающий предполагает что читатель знает, как работают основные логическиеоперации, а также знаком с понятием истинности, умеет строить таблицы истинности и можетдоказать что Α→ Β <=> ¬Α v B, а А ≡ B <=>(¬A^¬B) v (A^B) потому пропускает данный пунктУтверждениеЗапись P(x`) можно рассматривать как высказывание , если известны значения элементов x` атакже как отношение, которому принадлежит кортеж x`.Предложение 6.2Пусть P(x`), Q(x`) ⊊N^k — рекурсивные отношения.