- •Часть 1.
- •Оглавление
- •1. Модели дискретных структур. Комбинационные схемы
- •1.1. Введение
- •1.2. Функции алгебры логики
- •Коммутативность
- •Ассоциативность
- •Дистрибутивность
- •1.3. Булева алгебра. Функциональная полнота
- •Свойства алгебры Жегалкина
- •1.4. Минимизация функции алгебры логики
- •1.5. Функции k-значной логики
- •1.6. Основные понятия трехзначной логики
- •1.7. Представление k-значных функций в виде нормальных форм
- •1.8. Двоичное кодирование переменных и функций трехзначной логики
- •1.9. Программная реализация логических функций и автоматов
- •2. Формальные языки и грамматики
- •2.1. Введение в теорию формальных языков и грамматик
- •2.2. Выводы цепочек формального языка. Деревья ксг
- •2.3. Основные понятия теории формальных языков и грамматик
- •2.4. Приведение грамматик
- •2.4. Операции над языками
- •2.5. Право-линейная и автоматная грамматики
- •3. Теория автоматов
- •3.1. Введение
- •3.2. Способы представления конечных автоматов
- •3.3. Минимизация числа состояний автомата
- •3.4. Использование сети Петри при переходе от грамматики к автомату
- •3.5. Сети Петри. Маркировка
- •3.6. Классификация сетей Петри
- •Статические ограничения
- •3.7. Синхронные и асинхронные автоматы
- •3.8. Модели автоматов Мили и Мура
- •3.9. Кодирование автомата
- •3.10. Элементная база синтеза комбинационных схем
- •3.11. Структурный синтез автомата
- •4. Отдельные вопросы теории вычислительных процессов
- •4.1. Автоматы с магазинной памятью
- •4.2. Комбинационные схемы обнаружения ошибок
- •4.3. Пространство сообщений. Коды обнаружения и исправления ошибок
- •Контрольные вопросы
2.2. Выводы цепочек формального языка. Деревья ксг
Правила грамматики задают способы подстановки цепочек. Подстановка осуществляется заменой нетерминального символа в заданной цепочке на правую часть правила, левой частью которого является такой нетерминал.
Рассмотрим грамматику с аксиомой грамматики < S > и правилами вывода вида:
S a A B c 2. S 3. A c S B
4. A A b 5. B b B 6. B a
Если начать вывод цепочек языка, используя первое правило, то последовательность подстановок может быть следующей:
S a A B c ( 1 правило )
S a A b B c ( 5 правило )
S a A b b a c ( 6 правило )
S a c S B b b a c ( 3 правило )
S a c S a b b a c ( 6 правило )
S a c a b b a c ( 2 правило )
В рассмотренном выводе присутствует семь цепочек, включая начальную и заключительную.
Определение. Язык, задаваемый грамматикой, есть множество терминальных цепочек, которые можно вывести из начального символа грамматики.
Построим дерево вывода цепочки: a c a b a c , используя выше рассмотренную грамматику.
S
a A B c
A b a
c S B
a
Замечание. Для каждого дерева существует единственный левый и правый выводы, то есть вывод, когда на каждом шаге заменяется самый левый (правый) нетерминальный символ. Многие методы обработки языков рассчитаны исключительно на левый (правый) выводы. В подобных случаях пишут:
LB (L - left)
RB (R - right ).
Цепочке языка может соответствовать более чем одно дерево, так как она может иметь разные выводы, порождающие разные деревья. Если одна цепочка имеет несколько деревьев вывода, то говорят, что соответствующая грамматика неоднозначна.
2.3. Основные понятия теории формальных языков и грамматик
Пусть задан алфавит V терминальных символов. Множество всех конечных слов или цепочек в алфавите V обозначим V*.
Формальный язык L над алфавитом V - это подмножество множества V*, то есть L (V) V* [ 3 ].
Конструктивное описание формального языка осуществляется с помощью формальных систем, называемых формальными порождающими грамматиками.
Определение. Формальной порождающей грамматикой G называется формальная система, описываемая с помощью четырех формальных объектов
{ V, W, P, S }, где V - словарь терминалов, W - словарь нетерминалов, причем V W = , P - множество правил вида , где и ( V W ) ,
S - аксиома грамматики.
Определение. Цепочка называется выводимой из цепочки , если они представимы в виде:
= =
и в грамматике существует правило вида .
Определение. Цепочка называется выводимой из , если существует конечная последовательность цепочек вывода:
0 0 1, ..., k , где цепочка i непосредственно выводима из i-1 для всех i = 0,1,..., k-1.
Введем обозначение . Это значит, что выводима из
в грамматике G.
Определение. Языком L(G), порождаемым грамматикой G, называется множество всех цепочек, выводимых из аксиомы грамматики.
Определение. Грамматики G1 и G2 эквивалентны тогда и только тогда, когда они порождают один и тот же язык.
Классификация грамматик Холмского
Тип 0 - грамматика произвольного вида без ограничений на правила вывода.
Тип 1 - контекстная грамматика. Контекстная грамматика, правила которой имеют вид:
A , A W*, (V W)*,
где - непустая цепочка, и - контекст правила ( цепочки символов, которые не заменяются и не изменяются при его применении).
Тип 2 - контекстно-свободная грамматика (КСГ), правила которой имеют вид
A , (V W)*.
Тип 3 - регулярная грамматика, все правила которой имеют вид:
A B
A , V, B W.
Определение. Язык, порождаемый грамматикой определенного типа , называют языком такого же типа.
Пример. Определить тип языка, цепочки которого имеют вид
{ a, aaa, aaaaa ... a2n-1 .... }.
Решение. Определим объекты грамматики и определим ее правила, позволяющие строить цепочки заданного языка. Ими будут:
V = {a}, W = {S}, P = { S a a S, S a }.
Из всего следует, что это язык типа 2.
Пример. Определить тип языка булевых функций.
Решение. Грамматику зададим объектами:
G = {V, W, P, S}, V= { a, b, c, &, , , (, ) }, W = {S},
и правилами вида:
1. S ( S & S ) 4. S a
2. S ( S S ) 5. S b
3. S S 6. S c.
Анализ показывает, что это контекстно-свободная грамматика,
и язык, порождаемый ей, есть язык типа 2.
Пример. Определить тип языка, цепочки которого имеют вид
{ a b }.
Решение. Запишем правила, с помощью которых можно вывести цепочки заданного языка. Они имеют вид:
S a S b; S a b.
Как показывает анализ, заданный формальный язык принадлежит типу 2.