Теория алгоритмов, формальных языков, грамматик и автоматов. Бильгаева Н.Ц. - 25 стр.

    Независимо от указанных двух направлений развивалось построение формальных
моделей динамических систем. Для создания продуктивной теории эти модели должны были
быть, с одной стороны, достаточно узкими, а с другой - достаточно широкими, чтобы
охватить некоторый общий класс прикладных задач. Типичным примером такого рода
является модель конечного автомата. Эта модель позволяет описать многие процессы,
заданные на конечных множествах и развивающиеся в счетном времени, что позволило
создать для нее продуктивную теорию. Если в эту модель ввести бесконечность по какому-
либо параметру, то это приводит к общему классу систем, например, к машинам Тьюринга.
    Независимо и параллельно развивалась общая теория алгоритмов как ветвь современной
математики. Развитие вычислительной техники поставило перед математической теорией
алгоритмов новую задачу: стало необходимым классифицировать алгоритмы по различным
признакам. Эквивалентность понятий "алгоритм" и "машина Тьюринга" позволила
предположить, что поиски классификации алгоритмов окажутся связанными с поисками
промежуточных моделей между моделями конечного автомата и машиной Тьюринга.
    Таким образом, перечисленные четыре направления оказались тесно связанными. Теория
языков, порожденная чисто лингвистическими задачами, оказалась в центре интересов
математиков,      занимающихся       теорией алгоритмов, и ученых, разрабатывающих
абстрактные модели динамических систем и теоретические основы автоматики.
    Теория формальных языков и грамматик является разделом математической
лингвистики - специфической математической дисциплины,            ориентированной    на
изучение структуры естественных и искусственных языков. По характеру используемого
математического аппарата теория формальных грамматик и языков близка к теории
алгоритмов и теории автоматов.
    На интуитивном уровне язык можно определить как некоторое множество предложений
с заданной структурой, имеющих определенное значение. Правила, определяющие
допустимые конструкции языка, составляют синтаксис языка. Значение, или смысл фразы,
определяется семантикой языка.
    Если бы все языки состояли из конечного числа предложений, то не было бы проблемы
синтаксиса. Но, так как язык содержит неограниченное (или довольно большое) число
правильно построенных фраз, то возникает проблема описания бесконечных языков с
помощью каких-либо конечных средств.
    Различают следующие виды описания языков:
    1) порождающее, которое предполагает наличие алгоритма,             последовательно
порождающего все правильные предложения языка;
    2) распознающее, которое предполагает наличие алгоритма, определяющего
принадлежность любой фразы данному языку.

      4.2. Основные понятия порождающих грамматик
     Алфавит - это непустое конечное множество. Элементы алфавита называются
символами.
     Цепочка над алфавитом Σ={а1, а2, …, аn} есть конечная последовательность элементов
аi. Множество всех цепочек над алфавитом Σ обозначается Σ*.
     Длина цепочки х равна числу ее элементов и обозначается |x|. Цепочка нулевой длины
называется пустой и обозначается символом ε. Соответственно, непустая цепочка
определяется как цепочка ненулевой длины. Пусть имеется алфавит Σ={а, b}. Тогда
множество всех цепочек определяется следующим образом: Σ*={ ε, а, b, aa, ab, ba, bb, aaa,
aab, aba, . . .}.
     Цепочки x и y равны, если они одинаковой длины и совпадают с точностью до порядка
символов, из которых они состоят.
     Над цепочками x и y определена операция сцепления (конкатенации, произведения),
которая получается дописыванием символов цепочки y за символами цепочки x.