Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
нием, налагаемым не на объем памяти, а на способ ее использования; однако для всякого МП-автомата можно построить эквивалентный ему МП-автомат, у которого ни в одном вычислении длина используемой части рабочей ленты не превышает длины входной цепочки; такой МП-автомат можно рассматривать «почти» как частный случай ЛО-автомата («почти» потому, что МП-автомат имеет отдельную входную ленту, которой лишен ЛО-автомат; впрочем, это различие не является существенным, если мы интересуемся только объемом памяти).
12.3.2. Иерархия автоматов
Таким образом, критерий объема памяти, необходимого для проведения вычисления, позволяет дать следующую иерархическую классификацию автоматов:
Чтобы сделать эту классификацию более тонкой, — в частности, чтобы ввести в нее естественным образом МП-автоматы, — необходимо учитывать не только объем, но и структуру используемой при вычислении памяти. На этом пути можно определить ряд интересных подклассов автоматов.
Другое направление, в котором развивается теория автоматов,— это изучение автоматов, работающих в реальном масштабе времени, и вообще изучение классификаций автоматов по времени вычисления').
') Объем памяти и время работы могут рассматриваться как некоторые характеристики сложности вычисления в автомате. Существуют и другие характеристики сложности вычисления. Теория сложности вычислений, развитаяГл. XII. Грамматики непосредственно составляющих 201
Еще один важный критерий — детерминированность/недетерминированность автомата.
§ 12.4. УПРАЖНЕНИЯ
1. Построить ЛО-автоматы, допускающие языки
[апЬпап \п > 0}, {хсх\х є {а, Ь}*};
можно ли построить для этих языков детерминированные ЛО-автоматы?
2. Показать, что с помощью НС-правил можно выполнять перестановки; например, если имеется НС-грамматика G, порождающая язык, каждая цепочка которого имеет вид хсу, где х и у не содержат с, то можно построить НС-грамматику G', такую, что L(Of) = {усх\хсу Z=L(G)).
3. Пусть имеются ЛО-автоматы W1 и Ш2; построить ЛО-автомат
допускающий язык L(Wi)U L(sA2), и ЛО-автомат 91", допускающий язык L(sKl) П L(sK2).
Указание. Автомат W можно строить следующим образом. Рядом с любой входной цепочкой / пишем цепочку /', которая получается из / путем копирования ее символов и добавления к ним штрихов; затем та «часть» автомата Я, которая «совпадает с Яі», проверяет допустимость цепочки / относительно Si, а другая часть автомата Я, «идентичная автомату Яг» с точностью до штрихов, проверяет допустимость цепочки /' относительно Я2; завершение построения очевидно.
в работах Б. А Трахтенброта, Г. С. Цейтина, М. Рабина, М. Блюма и др., представляет собой один из важнейших разделов современной теории автоматов. Основные понятия и факты этой теории изложены в книге Б А. Трахтенброта «Сложность алгоритмов и вычислений», Новосибирск, 1967. — Прим. ред.Часть III АЛГЕБРАИЧЕСКИЙ ПОДХОД
Глава XIII ГОМОМОРФИЗМЫ ПОЛУГРУПП
В этой главе излагаются некоторые алгебраические понятия, которые не раз понадобятся нам в ходе дальнейшего изложения
§ 13.1. ПРОИЗВОЛЬНЫЕ ПОЛУГРУППЫ
13.1.1. О единичном элементе
Понятие полугруппы было определено в п. 1.1.3, и читатель вероятно, заметил, что всякая свободная полугруппа обязательно обладает единичным элементом. Нам будет удобно предположить, что и всякая полугруппа обладает таким элементом. Если же в данной полугруппе M единичного элемента нет, то мы всегда можем добавить к ней новый элемент Е, такой, что
(VZeM) [EX = XE = E]; EE = E.
В результате получится полугруппа (в том, что при добавлении E сохраняется ассоциативность, убедиться нетрудно), имеющая единичный элемент E и, очевидно, включающая в себя исходную полугруппу.
13.1.2. Естественный гомоморфизм
Пусть M = {А, В, С,.. .} — полугруппа с единицей и ЗЇ — отношение эквивалентности на М, совместимое влево и вправо с операцией композиции, т. е. конгруэнция. В гл. I было показано, что ЗЇ определяет разбиение M на непересекающиеся классы, составляющие фактормножество M/S?, причем классы А, В, U, ... образуют относительно индуцированной операции новую полугруппу с единицей. Там же рассматривался пример, в котором M была свободной полугруппой и ЗЇ — эквивалентностью в смысле Туэ.
Рассмотрим естественное (или каноническое) отображение if, связанное с 3?; каждому А е M отображение ^ ставит в соответствие его класс A в разбиении, индуцированном отношением Я.Г л. XIII. Г омоморфизм полугрупп
203
Для конгруэнции имеет место соотношение
т. е. образ композиции есть композиция образов.
Отображение ф называется естественным гомоморфизмом, ассоциированным с конгруэнцией SR.
Пример. Пусть M — свободная полугруппа над алфавитом % = {а, Ь, с} и Я — отношение, соответствующее равенству длин цепочек: пустая цепочка принадлежит классу 0, однобуквенные цепочки — классу 1 и т. п. Фактормножество 51*/31 изоморфно полугруппе с единицей, образованной множеством целых неотрицательных чисел относительно сложения.
13.1.3. Общие определения
Пусть M и M' — полугруппы с единицей, ф — отображение первой во (возможно, на) вторую. Говорят, что ф есть гомоморфизм M в (соответственно на) M', если