Исторические и библиографические замечания

Основная цель этих замечаний - указать различные общие направления, в которых развивается теория формальных языков, равно как дать советы по конкретным связанным с текстом вопросам, которые могут заинтересовать читателя. Мы не пытались во всех случаях указывать, какому конкретному автору (авторам) принадлежит каждый отдельный результат,- иногда это оказывалось затруднительным.

Материал первой главы восходит к [Т1] и [Т2], хотя у нас изложение существенно иное; к тому же мы использовали некоторые идеи из [МоН2] и заимствовали лемму 1.10 из [EhR4].

По проблематике второй главы имеется масса литературы. Материал по конечным автоматам и регулярным выражениям читатель может найти в монографиях [Sal] и [МсР]^*. Каждая из работ [Наг], [HU], [Май], [Sa2] содержит довольно полное изложение теории формальных языков и описание иерархии Хомского^**. В [AU] эта теория рассматривается с точки зрения теории компиляции. Теория контекстно-свободных языков излагается в монографиях [G₁] и [Be3]; из основных первоисточников этой теории укажем [ChS], [GR] и [Niv]. Большая и важная область - теория сложности формальных языков - совсем не обсуждается; мы отсылаем читателя к [AHU], [HU] и [Во]. В статье [K1] впервые сформулирована и доказана теорема Клини, а в [Ch] впервые рассматривались порождающие грамматики.

^* (На русском языке см. монографии [ТрБ^*] или [Ми^*].- Прим. перев.)

^** (Относительно прочей литературы по этим вопросам, в частности литературы на русском языке, см. послесловие.- Прим. перев.)

Доказательство теоремы 3.2 приводится в [DeS]; наше изложение следует в основном [Sal]. Два совершенно различных решения проблемы СКС (FPP) имеются в работах [ManS] и [Has]; наше изложение основывается на идеях последней из них. Постановка проблемы СКС принадлежит Я. Бжозовски.

Значительная часть первоначальных результатов относительно кодов была получена Шютценберже; [La] - одна из последних работ, по большей части теоретическая. Дополнительные сведения о максимальных кодах можно почерпнуть из [Map1] и [Мар2^*]. Множества совпадения и элементарные морфизмы были введены в [EhR1] и [EhR2]. Проблема соответствия Поста была впервые поставлена в [Р]; она подробно обсуждается в [Har], [Mau] и [Sa2].

Решение проблемы эквивалентности для DOL-последовательностей впервые было дано в [CuF]; мы привели здесь, гораздо более простое решение из [EhR2] и [RS]. Доказательство леммы 5.7 проводится по [Sa3]; дальнейшие ссылки по этому вопросу можно найти в [RS].

Основными источниками по локальным и k-проверяемым языкам являются [Niv] и особенно [McP]^*. Теорема 6.2 взята из [CuM]. Исходный вариант леммы 6.4 заимствован из [Gr1]. Теорема 6.5 изложена по [Sh]; приведенный вариант теоремы 6.7 представлен в [Gr2]. Дальнейшее обсуждение вопросов представления с использованием множеств совпадения читатель найдет в [BoB], [Cu], [CuM], [EnR], [RS] и [Sa5]. Теорема 6.11 впервые встречается в [St].

^* (Понятие локального языка и теорема 6.1 по существу содержатся в статье [Мед^*]; см. также примечание на с. 98.- Прим. перев.)

Первой работой, посвященной грамматическим формам, была [CrG]; однако в ней дано несколько иное определение интерпретации терминалов, при котором нельзя использовать морфизмы. Материал трех параграфов гл. 7 заимствован из [MSW2], [MSW3] и [MSW4] соответственно^*.

^* (См. также [MSW5^*].- Прим. перев.)

Приведенный ниже список литературы содержит только те работы, на которые даются ссылки, и ни в коем случае не претендует на роль библиографии по теории формальных языков или перечня лучших работ в этой области. Многие из перечисленных в нем книг содержат обширную библиографию.