1610906280-c80d8404f2eaa01776b47d41b0f18e85 (824375), страница 8
Текст из файла (страница 8)
. . ak A, где a1 , . . . , ak — терминальные символы, A — нетерминальный символ, то на всех последующих шагах префиксa1 a2 . . . ak останется неизменным. Похожим свойством обладают конечные автоматы,которые не имеют памяти вне процессора и в которых символы слов также прочитываются слева направо.
Это наблюдение лежит в основе следующей теоремы.Теорема 11. Имеют место следующие два утверждения:1) Если язык L порождается регулярной грамматикой, то L — автоматный.2) Если L — автоматный язык, то L \ {Λ} порождается регулярной грамматикой.Доказательство. Сначала докажем первое утверждение теоремы.
Пусть язык L порождается регулярной грамматикой Γ = hV, T, P, Si. Определим недетерминированный конечный автомат A следующим образом:а) Множеством состояний автомата является множество V ∪ {q}, где q — новыйсимвол, т. е. q ∈/ V.б) Внешним алфавитом автомата будет множество T .в) Начальным состоянием является S.г) Единственным выделенным состоянием будет q.д) Переходы в автомате A определяются по следующему принципу. Для каждойaпродукции вида A −→ aB добавляем дугу °−−−−→°. Для каждой продукцииABaA −→ a добавляем дугу °−−−−→°◦.qAПокажем, что L = T (A).
Пусть w = a0 a1 . . . ak ∈ T ∗ — произвольное слово. Тогдаимеет место следующая цепочка эквивалентных утверждений:w ∈ L ⇐⇒ Существует вывод S −→ a0 A0 −→ a0 a1 A1 −→ . . . −→ a0 . . . ak−1 Ak−1ΓΓΓΓ−→ a0 . . . ak−1 ak слова w в грамматике Γ. ⇐⇒ В множестве P имеются продукцииΓвидаS −→ a0 A0A0 −→ a1 A1... ... ...Ak−2 −→ ak−1 Ak−1Ak−1 −→ ak⇐⇒ В построенном автомате A имеется путь видаa0 - i a1 - i a2 - . . .H© iSA0A1ak−1- i ak - idqAk−1§ 9. Свойства формальных грамматик31⇐⇒ w = a0 a1 . . . ak ∈ T (A). Что и требовалось доказать.Теперь докажем второе утверждение теоремы. Пусть L распознается конечнымавтоматом A. В силу леммы о вахтере можно считать, что A обладает свойствомвахтера.
Преобразуем автомат A в автомат A0 , сделав начальное состояние невыделенным, если оно было выделенным в A. Ясно, что L \ {Λ} = T (A0 ). Пусть A0 =hQ, A, δ, q0 , F i. Определим регулярную грамматику Γ следующим образом:а) Множеством нетерминальных символов грамматики является множество Q.б) Множеством терминальных символов будет множество A.в) Начальным символом является q0 .г) Множество продукций определяется по следующему принципу. Для каждой дуaги автомата вида ° −−−−→° добавляем продукцию q1 −→ aq2 .
Кроме этого,q1q2если состояние q2 является выделенным, то добавляем дополнительно продукцию q1 −→ a.Покажем, что L \ {Λ} = L(Γ). Ясно, что пустое слово не принадлежит обеимчастям этого тождества. Пусть w = a1 . . . ak ∈ A∗ — произвольное непустое слово.Тогда имеет место следующая цепочка эквивалентных утверждений:w ∈ L ⇐⇒ В автомате A0 существует путьa1 - i a2 - i a3 - . . .H© iq0q1q2ak−1- i ak - idqk−1qkвдоль которого распознается слово w.
⇐⇒ В построенной грамматике Γ имеютсяпродукцииq0 −→ a1 q1q1 −→ a2 q2... ... ...qk−2 −→ ak−1 qk−1qk−1 −→ ak⇐⇒ Существует вывод q0 −→a1 q1 −→a1 a2 q2 −→ . . . −→ a1 . . . ak−1 qk−1 −→a1 . . . ak−1 akΓΓΓΓслова w в грамматике Γ. ⇐⇒ w ∈ L(Γ). Что и требовалось показать.ΓЗамечание. Предыдущая теорема позволяет утверждать, что класс автоматныхязыков почти совпадает с классом языков, порождаемых регулярными грамматиками.
Иногда в литературе дается несколько другое определение регулярной грамматики, в котором допускается возможность вывода пустого слова. Это делается длятого, чтобы избавиться от слова почти в предыдущем утверждении. При таком расширенном определении класс автоматных языков в точности равен классу языков,порождаемых регулярными грамматиками.Теперь мы докажем важное свойство разрешимости любого языка, порождаемогонеукорачивающей грамматикой. Под разрешимостью языка L над алфавитом A мыпонимаем существование алгоритма, который по любому слову w ∈ A∗ за конечноечисло шагов позволяет определить, принадлежит ли w языку L или нет. Ниже мы32Глава II. Конечные автоматы и формальные грамматикиприведем лишь неформальное описание разрешающей процедуры для языка, порожденного неукорачивающей грамматикой.
В наших рассуждениях мы будем опиратьсяна интуитивную эффективность таких процедур, как непосредственное получениеодного слова из другого по правилам заданной формальной грамматики; проверка принадлежности заданного слова конечному множеству, имеющему эффективноеописание; и др.В формулировке следующего утверждения через |V ∪ T | мы обозначаем количество элементов в конечном множестве V ∪ T .Предложение 12. Пусть Γ = hV, T, P, Si — неукорачивающая грамматика. Если∗α −→ β, то в Γ существует вывод α −→ . .
. −→ β, содержащий не более |β|·|V ∪T ||β|ΓΓΓслов.Доказательство. Пусть имеется вывод α = α0 −→ α1 −→ . . . −→ αn = β. Так какΓΓΓΓ — неукорачивающая, то 1 6 |α0 | 6 |α1 | 6 . . . 6 |αn |. Разобъем данный вывод нанесколько участков, каждый из которых состоит из слов одинаковой длины:α −→ . . . −→ αi0 −→ αi0 +1 −→ .
. . −→ αi1 −→ . . . −→ αik−1 +1 −→ . . . −→ αik ,{z}|{z}|0|{z}слова длины |α0 |слова длины |α0 |+1слова длины |αn |где k = |αn | − |α0 | и ik = n.Рассмотрим произвольный участок, состоящий из всех слов длины m. Заметим,что количество слов длины m над алфавитом V ∪ T равно |V ∪ T |m . Поэтому, если рассматриваемый участок содержит более, чем |V ∪ T |m элементов, то среди нихнайдутся одинаковые слова αi = αj , i < j. Следовательно, вывод можно укоротить,удалив участок αi −→ . . . −→ αj .
Повторив, если потребуется, аналогичные рассуждения несколько раз, мы добьемся того, что слов длины m в нашем выводе окажетсяне более, чем |V ∪ T |m штук.Применив описанную процедуру ко всем m, мы получим новый вывод слова β изα, в котором суммарное количество слов не превосходит|V ∪ T ||α0 | + |V ∪ T ||α0 |+1 + . .
. + |V ∪ T ||αn | 66 |V ∪ T ||αn | + |V ∪ T ||αn | + . . . + |V ∪ T ||αn | =|{z}|αn |−|α0 |+1= (|αn | − |α0 | + 1) · |V ∪ T ||αn | 6 |αn | · |V ∪ T ||αn | .Что и требовалось доказать.Теорема 13. Пусть Γ = hV, T, P, Si — неукорачивающая грамматика. Тогда языкL(Γ) разрешим, т. е. существует алгоритм, который по любому слову w ∈ T ∗ законечное число шагов позволяет определить, порождается ли w в грамматике Γили не порождается.Доказательство. Пусть w — произвольное слово в алфавите T . Алгоритм имеетследующее описание.
Сначала вычисляем натуральное число k = |w| · |V ∪ T ||w| .Затем строим конечную последовательность A1 , A2 , . . . , Ak конечных множеств словпо индукции:A1 = {S},An+1 = An ∪ {v ∈ (V ∪ T )∗ | v непосредственно получаетсяиз некоторого u ∈ An в грамматике Γ}.§ 9. Свойства формальных грамматик33Заметим, что для любого 1 6 n 6 k множество An состоит из всех слов, имеющихвывод в грамматике Γ, длина которого не превосходит n.
В силу предыдущего предложения имеет место эквивалентность w ∈ L(Γ) ⇐⇒ w ∈ Ak . Следовательно, еслиусловие w ∈ Ak выполнено, то w порождается заданной грамматикой, в противномслучае — не порождается.Следствие 14. Если язык L принадлежит одному из следующих классов, то Lразрешим:a) класс языков, порождаемых контекстно-свободными грамматиками;б) класс языков, порождаемых регулярными грамматиками;в) класс автоматных языков.Доказательство.
Разрешимость языков из пунктов (а) и (б) следует из теоремы 13.Если L — автоматный язык, не содержащий пустого слова, то его разрешимостьследует из пункта (б) и теоремы 11. Если же L — автоматный и Λ ∈ L, то в силупункта (б) и теоремы 11 язык L1 = L \ {Λ} разрешим. Следовательно, язык L =L1 ∪{Λ} также разрешим, поскольку он получен из L1 добавлением пустого слова.Глава IIIФормализации понятия вычислимойфункцииОсновной целью данной главы является формализация понятия вычислимой функции, действующей на натуральных числах. Напомним, что n-местной частичнойфункцией на ω мы называем любую функцию вида f : X → ω, где X ⊆ ω n , n ∈ ω.Существует несколько различных подходов, приводящих к тому или иному определению частичной вычислимой функции.
Мы рассмотрим четыре подобных подходаи покажем, что все они эквивалентны. Первая из формализаций, с которой мы познакомимся в следующем параграфе, связана с машинами Шёнфилда [8], [13].§ 10.Машины ШёнфилдаПрограмма:Счетчиккоманд0: Команда 01: Команда 1HH© 2: Команда 2©...n: Команда nAA¢¢r0 r1 r2рег. рег. рег.#0 #1 #2............rk rk+1 .
. . . . .рег. рег. . . . . . .#k #k+1Машина Шёнфилда — это механическое вычислительное устройство, хотя окончательная его формализацияявляется совершенно математической.Тем не менее, мы ограничимся только«механическим» описанием.Машина Шёнфилда однозначно задается:1) Бесконечным множеством регистров, пронумерованных натуральными числами 0, 1, 2, .
. .Каждый регистр — это ячейка памяти, способная содержатьлюбое натуральное число.Содержимое регистров может меняться по ходу вычислений. Отметим, что каждаяконкретная машина Шёнфилда использует в своих вычислениях только конечноечисло регистров. Основное назначение регистровой памяти — это хранение входных,промежуточных и выходных данных.2) Счетчиком команд, являющимся особой ячейкой памяти, которая в каждыйданный момент содержит некоторое натуральное число. Счетчик команд указывает на номер команды в программе, которая исполняется в данный момент.В начальный момент в счетчик команд заносится 0.§ 10.
Машины Шёнфилда353) Программой, содержащейся в отдельной выделенной памяти машины. Программа — это конечный список команд, последовательно пронумерованных натуральными числами от 0 до некоторого n ∈ ω. В ходе вычислений программа неменяется, она фиксирована.Шаг машины состоит в исполнении той команды из программы, номер которойуказан в данный момент в счетчике команд. Если команды с таким номером в программе нет, то машина останавливается.Существует только два типа команд:1) INC iПри исполнении данной команды машина увеличивает содержимое i-го регистра и счетчик команд на 1, после чего переходит к следующему шагу в своейработе.2) DEC i, nЕсли к началу исполнения данной команды содержимое i-го регистра больше0, то машина уменьшает его на 1 и заносит n в счетчик команд. Если же в данный момент содержимое i-го регистра равно 0, то машина увеличивает счетчиккоманд на 1.Еще раз подчеркнем, что машина останавливается тогда и только тогда, когда всчетчик команд заносится номер несуществующей в программе команды.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
