Научная литература
booksshare.net -> Добавить материал -> Лингвистика -> Гросс М. -> "Теория формальных грамматик " -> 68

Теория формальных грамматик - Гросс М.

Гросс М., Лантен А. Теория формальных грамматик — М.: Мир, 1971. — 296 c.
Скачать (прямая ссылка): teoriyaformalnihgrammatik1971.djvu
Предыдущая << 1 .. 62 63 64 65 66 67 < 68 > 69 70 71 72 73 74 .. 101 >> Следующая


нием, налагаемым не на объем памяти, а на способ ее использования; однако для всякого МП-автомата можно построить эквивалентный ему МП-автомат, у которого ни в одном вычислении длина используемой части рабочей ленты не превышает длины входной цепочки; такой МП-автомат можно рассматривать «почти» как частный случай ЛО-автомата («почти» потому, что МП-автомат имеет отдельную входную ленту, которой лишен ЛО-автомат; впрочем, это различие не является существенным, если мы интересуемся только объемом памяти).

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', если
Предыдущая << 1 .. 62 63 64 65 66 67 < 68 > 69 70 71 72 73 74 .. 101 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed