Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Лекция 4
Исчисления. Формальные системы.
Формальные грамматики. Автоматы
Существует класс задач, математические модели и алгоритмы, решения которых удобно представлять в виде формальных исчислений. Наряду с машиной состояний и функциями, вычислимыми алгоритмом, «алгоритм–исчисление» является третьим видом уточнения понятия алгоритма. Технология проектирования программ, основанная на формальных исчислениях, обладает определённой спецификой, которая и рассматривается в этой лекции.
1. Исчисления и формальные системы
Содержательно исчисление задаёт конструктивный способ порождения слов некоторого языка. Например, исчисление конечных разностей Ньютона даёт возможность порождать (исчислять) для некоторого правильного выражения формул с дифференциалами все эквивалентные ему выражения, заданные правилами тождественных преобразований. Исчисление высказываний позволяет конструктивно порождать, все возможные логические законы в виде тождественно истинных высказываний. Исчисление предикатов позволяет строить формальные теории в виде системы формул, которые истинны в выбранной интерпретации.
1.1. Исчисление Туэ (Норвежский математик Туэ в 1912 г. сформулировал наиболее общую модель исчисления)
где – конечный алфавит
– правила подстановок, где , ( – слова из алфавита А). А* – все слова в алфавите А; правила «работают» в обе стороны.
ИТ позволяет конструктивно решить две основных задачи – задачу порождения и задачу распознавания слов, входящих в ИТ.
а) Задача порождения эквивалентных слов в ИТ.
Задано слово , породить все возможные слова W, выводимые из Z по правилам Р из ИТ. Множество слов , выводимых из Z, называются классом эквивалентности по Z, а все , такие, что из , называются эквивалентными (W).
б) Задача распознавания эквивалентности пары слов .
ZW (эквивалентны), если из Z выводимо слово W по правилам Р .
Порядок применения правил при решении задач не регламентирован и осуществляется в соответствии с деревом полного перебора.
Пример 1: , где – пустое множество . Слово представляет собой строку Маркова.
Слово «аbа» в этом ИТ выводимо несколькими путями (последовательностями применения правил).
1.2. Исчисление Эрбрана – Гёделя. (ИЭГ)
В 1934 г. Эрбран и не независимо от него Гёдель в качестве уточнения понятия алгоритма построили формальное исчисление для вычисления всех возможных функций на множестве натуральных чисел.
, где
а) А = {цифры, знаки функций, знак операции следования «F+1», имена переменных (буквы латинского алфавита)}.
б) ППФ – правильно построенные формулы, которые состоят из термов, построенных по правилам, принятым в математике, и имеющих вид – , где и – термы.
в) .
– подстановка знака цифры вместо имени переменной
– замена (подстановка) терма на цифру (число).
Пример 2. Задана система ППФ.
1. .
2. .
Вычислить функцию при значениях
Применение
1.
2.
Если определить системой ППФ как операцию сложения
натуральных чисел
3.
4. ,
то по правилу .
2. Формальные системы (ФС)
Формальная система суть исчисление, где выделено подмножество формул (слов), которое объявлено изначально выводимым. Эти формулы называются аксиомами.
а) ППФ – правильно построенные формулы в алфавите А,
б) ; А* – множество слов построенное в алфавите А.
в) – аксиомы являются подмножеством ППФ.
г) ПВ – правила вида , что означает, из совокупности ППФ выводима ППФ. В любой ФС множество формул ППФВ выводятся из ППФА с помощью правил ПВ. При этом {ППФВ}{ППФ}, – называются выводимыми формулами.
3. Формальные грамматики (ФГ)
Исчисление в виде ФС предложено американским математиком Хомским (1953 г.) сначала для решения проблем структурной лингвистики, а далее описания формальных языков программирования.
ФГ=<А, V, S, P>, где А – терминальный алфавит
– вспомогательный алфавит, S – единственная аксиома, Р – правила вида и , где .
ФГ порождает характерный язык в виде подмножества слов. Правила ФГ не содержат никаких ограничений на рекурсивность подстановок.
4. Автоматы и грамматики
Основные определения.
а) Конечный алфавит – терминальный алфавит (малые латинские буквы).
б) – все слова, полученные из букв алфавита, – операция итерации приписывания (конкатенации). Например слово = aabcc получено из «а» приписыванием буквы «а» к букве «а» – далее получено последовательным приписыванием к слову букв .
в) – язык, вообще говоря, состоит из бесконечного числа слов. Возникает проблема описания языка при помощи конечных и конструктивных объектов (например, формул или правил порождения).
Как обычно, рассматриваются две основные задачи.
г) Порождение языка L. Для порождения слова служит специальная конструкция – порождающая грамматика G, которая представляет собой конечный набор продукций (правил подстановок) для вывода любых слов языка из специального символа S (аксиомы) и только их.
Формально –
A – основной алфавит, V – вспомогательный алфавит, – аксиома
– объединённый алфавит, , Р – правила (подстановки, продукции): имеет вид , где (в общем случае) (слова в объединённом алфавите)
д) Распознавание слов языка L. Дано слово , определить или . Для решения этой задачи служат распознающие автоматы. Формально автомат определяется – , где А – основной алфавит, S – алфавит состояний, Р – правила вида, si, wiSj, ,
4.1. Автоматная (регулярная) грамматика – AГ и
конечный автомат – КА.
Автоматная грамматика , где А – основной алфавит; Р – правила вида – аксиома. Конечный автомат , где А – основной алфавит; S – алфавит состояний; s0 – начальное состояние; sk – конечное состояние; Р – правила вида
Пример 3. Для языка L1 заданы:
а) б)
множество состояний автомата
V =
– маркер конца слова
АГ – правила порождения КА – правила перехода
1. 1.
2. 2.
3. 3.
4. 4.
АГ порождает слова языка L1 КА распознаёт слова языка L1.
Если заданы правила АГ, то правила КА получаются формальными переносами символов A из правой части правил в левую (см. пример). Если заданы правила КА, то правила АГ переносом символов A в правую часть правил.
КА задается графом переходов и по сути является машиной состояний (SM).
Кроме того, автоматный язык задается регулярным выражением (формулой из букв А, знаков операций: «» – конкатенация, «» – итерация, «» разделённое «или»). Для примера 3 регулярное выражение для L1 = ().
Пример 4. Пусть для языка L2 на рисунке задан граф КА и слово , говорят, что распознаётся КА, если находясь в под действием попадает в .Слово не распознаётся КА; КА из S0 под действием w2 останется в S1, т.к. нет правила выводящего из S1 под действием какого-либо символа кроме «b» и «».
Регулярное выражение для языка ,слова которого распознаются КА.
Пример 5. Вывод некоторого слова в АГ из примера 3.
Вывод слова aaacbbb. В кружочках отмечены номера правил.
4.2. Теоремы Клини. (прямая и обратная)
а) По регулярному выражению может быть построен КА
б) По КА может быть построено регулярное выражение
Формально любая машина состояний является конечным автоматом и поэтому на SM распространяется теорема Клини.
5. Контекстно-свободные грамматики и магазинные
автоматы. Контекстно-свободные языки.
Существуют языки, которые не могут быть описаны регулярным выражением и соответственно не может быть построен КА, который распознавал бы слова этого языка.
Пример такого языка , где … Количество a и b в слове L3 одинаково, например, слово, а слово .
Контекстно-свободная грамматика (КСГ).
A – алфавит языка (терминальный алфавит) = ; V – вспомогательный алфавит = , где – начальный символ – аксиома («начало»); – объединённый алфавит Р – правила вида , где , – слово из букв объединённого алфавита.
Пример 6. Порождающая грамматика для
Порождающие правила (подстановки, продукции)
1. Вывод слова aaacbbb
2. S
aSb
aaSbb
aaaSbbb
aaacbbb
В отличие от АГ грамматики из примера 3, которая порождает слова и в том числе , KCГ из примера 6 порождает слова с равным количеством «a» и «b» и только их.
Языки, которые порождаются КС – грамматиками называются контекстно-свободными языками.
5.1 Практические примеры применения КС-грамматик.
Первое практическое применение КСГ нашли для описания синтаксиса языков программирования. В частности в 1958 г. для описания языка Алгол была введена спецификация, т.н. нормальная форма Бэкуса – Наура (БНФ).
БНФ – формальная система для описания синтаксиса языков программирования. Впервые была изложена в отчёте Дж. Бэкуса «Algol 60 Report» (редактор П. Наур). БНФ фактически представляет собой форму описания любой контекстно-свободной грамматики. Эквивалентность записи БНФ и КСГ впервые отметил В.М. Курочкин в 1960–м году.
Пример 7. Формальное определение понятия «число со знаком»
а) БНФ – <число со знаком> :: = <число>+ <число>– <число>
Введём алфавиты
А(терминальный) = ,
где а – число, А – число со знаком.
б) правила КС-грамматики, порождающие понятие число со знаком.
Пример 8. КСГ для некоторого фрагмента арифметического выражения.
Правила подстановок для КСГ с комментариями их семантики.
Вывод слова (арифметического выражения) в КСГ показан на рис.1.
КСГ может быть использована и как распознающее (допускающее) слово средство. Пусть дано слово w, если удаётся построить обратный вывод от слова w, сворачивающий его до аксиомы (в примере 8 по правилу 1: ТА), то говорят, что , если сворачивание не возможно, то . Алгоритм сворачивания похож на поиск пути в лабиринте, где слова суть комнаты, а коридоры суть правила, вход суть исходное слово, выход суть аксиома. Так строится программа для синтаксических анализаторов
А В связи с тем, что грамматика не является
машинным алгоритмом, а алгоритмом –
Т исчислением, порядок порождения (приме-
нения правил) не является единственным.
АТ Например, вывод может пойти другим
(альтернативным) путём.
АА
А(А)
А(Т+А)
А(Т+Т) А(Т+Т)
Т(Т+Т) А(а+Т)
А*Т(Т+Т) A(a+a)
и т.д.
ТТ(Т+Т)
аТ(Т+Т)
аа(а+а)
и т.д. правило 6
Внимание !Параллельная подстановка запрещена!
Рис.1. Вывод «арифметического выражения».
5.2 Магазинный автомат (МА) или по другому push-down автомат.
Распознающее устройство для слов КС-языка представляет собой КА сцепленный с магазинной памятью (стеком).
Содержательно работа магазинного автомата описывается следующим образом.
При «заряжании» символа в магазин все символы проваливаются на одну позицию (пружина сжимается»), при «выстреле» выстреливается верхний символ магазина (только один), пружина разжимает и сдвигает всё содержимое магазина на одну позицию вверх. При холостом выстреле – магазин не изменяется.
Принцип действия похож на работу винтовки – автомата, например, АК–72 или М–16, (заряжается – по одному патрону, стреляет одиночными выстрелами).
А – алфавит входных символов на входной ленте, – маркер конца ленты, не входящий в А.
V – алфавит магазина = – маркер конца магазина, алфавит состояний .
Р – правила работы МА 4–х типов.
1. . МА находится в состоянии Si, считы-
вает входной символ а, смотрит на
символ А «макушки» МА, переводит МА в состояние Sj, «заряжает»» магазин, помещая символ В в «макушку» магазина, и протягивает входную ленту на одну позицию
2. всё по аналогии с правилом 1, но удаляет «выстреливает» символ из «макушки» магазина
3. всё по аналогии с правилом 1, не меняет содержимое магазина
4. входная лента пуста, магазин, МА оста-
навливается
Пример 9. Построение МА, распознающего слова языка (см.пример 6).
Руководящая идея: Автомат должен проверить равенство количества букв а и b. Для этого входные символы а поступают в магазин и кодируются символом А. Символ «с» перебрасывает МА в новое состояние. В этом состоянии МА «сравнивает» «А» с b и, если есть соответствие «выстреливает» А. Так происходит до тех пор, пока МА не встретит маркер «», в этой ситуации все символы А должны быть «выстрелены» (магазин пуст) и МА увидит в «макушке» магазина маркер Z0 пустоты магазина.
Правила работы МА (из примера 8).
– алфавит входной ленты, – алфавит состояний Начальная ситуация: с входной ленты считывается символ а, состояние МА – S0, магазин пуст – Z0. (см. таблицу протокола)
Правила работы МА.
1. начало работы
2. забивка магазина
3. cмена состояния на холостом ходу
4. выстреливание А при соответствии с
входным b
5. конец работы при правильном входном
слове
Протокол работы МА. (последовательность смены ситуаций)
|
Ситуация |
Такты |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
Входная лента |
A |
a |
a |
c |
b |
b |
b |
|
||
|
Магазин |
Z0 |
A Z0 |
A A Z0 |
A A A Z0 |
A A A Z0 |
A A Z0 |
A Z0 |
Z0 |
Z0 |
|
|
Состояние |
S0 |
S0 |
S0 |
S0 |
S1 |
S1 |
S1 |
S1 |
Sk |
|
|
Правило |
1 |
2 |
2 |
3 |
4 |
4 |
4 |
5 |
а) Для подготовки автомата к работе над следующим символом необходимо перевести его в состояние S0.
б) Если автомат не может в ситуации применить ни одно из правил, загорается аварийная лампа – слово L.
Протокол заполняется последовательно, начиная с начальной ситуации , далее к ситуации применяется правило 1 и т.д.. Например, в 3–м такте к ситуации применяется правило 3 и переводит в ситуацию .
6. Другие пары порождающая грамматика –
распознающий автомат для более сложных языков
контекстно-зависимый язык
КСГ имеет правила вида:
, где А – вспомогательный символ,
– слова, составленные из букв алфавита А и
вспомогательного алфавита V.
Свойства КЗГ
а) , – называется контекстом, который сохраняется в левой и правой части правил подстановок.
б) – не может быть пустым символом, поэтому КЗГ ещё называется неукорачивающей грамматикой.
КЗГ применяется в математической лингвистике для анализа естественных языков, там они называются грамматикой непосредственно составляющих (НС – грамматики).
Языки, которые порождаются КЗ-грамматиками, называются КЗ-языками.
6.2 Распознающий линейно ограниченный автомат (ЛОА)
Представляет собой машину Тьюринга (МТ) с ограниченной длиной входной ленты, которая называется линейно-ограниченным автоматом (ЛОА).
l – длина слова. L – длина ленты (память) L = a + bl,.
где a, b целые числа.
Обычно ЛОА имеют . Доказано, что такое ограничение не уменьшает класс КЗ – языков, которые распознаёт ЛОА.
6.3 Произвольные грамматики с правилами вида , где порождают произвольно сложные языки. Слова таких языков распознаются только машинами Тьюринга с неограниченной памятью ленты.
7. Иерархическая классификация формальных языков
Хомского.
В 1959 г. американский лингвист Хомский ввёл понятие формальной грамматики и порождаемого ею языка. Ввёл четыре класса языков. Названия языков существуют в определении Хомского.
Языки класс «0» (произвольные) не употребляются для практических целей.
Языки класса «1» (контекстно-зависимые); ЛОА, КЗ-грамматики используются для построения программ – переводчиков с естественных языков.
Языки класса «2» (контекстно-свободные); МА, КС-грамматики используются для построения синтаксических анализаторов языков программирования.
Языки класса «3» (автоматные языки); КА, А – грамматики используются для построения текстовых редакторов и отладчиков программ. Например, МЕ, Perl и т.д.
61