Next:2.3
Формулы и программы
Up:2
Словарь понятий, используемых в заданиях
Previous:2.1
Графы и системы дорог
Лексикографический порядок на словах одинаковой длины определяется
следующим образом: говорят, что слово
предшествует слову
(обозначаем
),
если существует такой индекс
,
что
и
для всех
Например,
и
Контекстно-свободная грамматика (здесь мы будем называть ее просто
грамматикой)
-- это четверка ,
где
1)
-- алфавит нетерминальных символов или нетерминалов ( нетерминалы
будут обозначаться либо прописными буквами, либо курсивными
словами, составленными из букв , цифр и дефиса);
2)
-- алфавит терминальных символов или терминалов (
);
3)
-- начальный нетерминал;
4)
-- конечное множество правил вывода, каждое из которых имеет вид
,
где левая часть правила
,
а правая часть
-- слово в алфавите
.
Как правило, мы будем рассматривать такие грамматики, в которых правые
части всех правил -- непустые слова. Слово в алфавите выводимо
из нетерминала
,
если существует его вывод из
-- последовательность слов
такая, что
,
и каждое
получается из
применением
некоторого правила вывода
из
,
т.е. заменой некоторого вхождения символа
в
на слово
.
Слово выводимо
в грамматике
,
если оно выводимо из ее начального нетерминала
;
при этом соответствующий вывод
называется выводом
в грамматике
.
Множество всех слов в алфавите терминалов ,
выводимых в грамматике
,
называется языком грамматики
и обозначается
.
Две грамматики
и
эквивалентны,
если
.
Грамматика называется удлиняющей, если длины слов правых частей всех ее правил больше 1.
Пример грамматики:
.
Эта грамматика -- удлиняющая, ее язык -- это все симметричные слова
четной ненулевой длины в алфавите .
Приведем вывод слова
в этой грамматике:
Правило
мы будем записывать также в виде
.
При записи множеств правил с одной и той же левой частью часто используют
следующее сокращения:
a) вместо
пишут
или
б) вместо двух правил
и
пишут
.
Синтаксическим анализатором внешнего представления понятия, заданного
с помощью синтаксических правил, называется такая программа, которая вводит
произвольный текст и либо печатает сообщение о том, что этот текст построен
в соответствии с правилами внешнего представления этого понятия (когда
это действительно так), либо сообщает одну или несколько причин, из-за
которых этот текст не является внешним представлением соответствующего
понятия.
Автоматная диаграмма
над алфавитом
задается конечным множеством вершин (среди которых выделены начальная
и конечная) и набором дуг. Из каждой вершины исходит ровно
дуг, помеченных попарно различными символами из
.
В отличие от орграфа в диаграмме одну и ту же пару вершин могут соединять
несколько дуг; могут быть и петли. Всякий путь от начальной вершины к конечной
задает слово в алфавите
,
получающееся последовательным выписыванием пометок дуг этого пути. Множество
всех таких слов обозначается
и называется языком автоматной диаграммы
.
Автоматные диаграммы
и
эквивалентны,
если
.
Рис. 11. Пример эквивалентных автоматных диаграмм:
(а) и
(б)
На рис. 11 приведен пример двух эквивалентных автоматных диаграмм. В
диаграмме
вершина 1 начальная, 2 конечная, в
вершина 1 начальная, а 3 конечная.
Две вершины
и
автоматной диаграммы называются несклеиваемыми, если
а) либо одна из этих вершин конечная, а другая нет,
б) либо существует символ
такой, что вершины
и
,
к которым ведут помеченные символом
дуги, выходящие из вершин
и
соответственно, несклеиваемые.
Все остальные пары вершин автоматной диаграммы называются склеиваемыми.
Например, в диаграмме
на рис. 11 вершины 1 и 2 склеиваемые, остальные пары несклеиваемые.
-машиной
называется вычислительное устройство, которое состоит из памяти, программы,
счетчика команд и счетчика ячеек.
Память -- это последовательность из ячеек
(переменных типа 0..1), занумерованных числами
называемых адресами ячеек.
Программа -- это последовательность из
команд, занумерованных числами
называемых метками.
Счетчик команд -- это переменная
типа
которая хранит метку текущей команды.
Счетчик ячеек -- это переменная
типа
которая хранит адрес текущей ячейки.
Имеются команды следующего вида:
-- присваивает текущей ячейке значение .
-- увеличивает
на
,
-- уменьшает
на
,
-- устанавливает CK
равным
,
-- изменяет CK
на
,
если текущая ячейка содержит 1,
-- команда останова.
Работа -машины
начинается при СК=СЯ=1и нормально завершается командой останова.
При работе она реализует вычисление функции
,
где
-- двоичные слова длины
.
Аргумент
-- это начальное состояние памяти, он допустим, если вычисление нормально
завершается. Результат
-- это содержимое памяти в момент выполнения команды останова.
Next:2.3
Формулы и программы
Up:2
Словарь понятий, используемых в заданиях
Previous:2.1
Графы и системы дорог