Регулярные языки и грамматики

Понятие формального языка

До начала XX века наука о языках – лингвистика – сводилась в основном к изучению естественных языков (русского, английского, латинского и т. д.), их классификации, выяснению сходств и различий между ними.

Возникновение и развитие метаматематики, изучающей по существу язык математики, логико-философские исследования языка науки, предпринятые Л. Виттгенштейном, Р. Карнапом и другими в 20-30 гг. XX века, идеи структурного подхода к лингвистике привели в 30-х годах к существенно более широкому представлению о языке, при котором под языком понимается всякое средство общения, состоящее из

1) знаковой системы, т. е. множества допустимых последовательностей знаков;

2) множества смыслов этой системы;

3) соответствия между последовательностями знаков и смыслами, делающего осмысленными допустимые последовательности знаков.

Знаками могут быть буквы алфавита, математические обозначения, звуки и т. д. Наука об осмысленных знаковых системах называется семиотикой. Наиболее продвинутыми являются исследования знаковых систем, в которых знаками являются символы алфавитов, а последовательностями знаков – тексты. К таким знаковым системам относятся естественные языки, языки науки, а также языки программирования. Именно интерес к языкам программирования, совпавший с новыми подходами в структурной лингвистике и необходимостью решать задачу машинного перевода естественных языков, привел в 50-х гг. к возникновению новой науки – математической лингвистики, которая рассматривает языки как произвольные множества осмысленных текстов.

Правила, определяющие множества текстов, образуют синтаксис языка; описание множества смыслов и соответствия между тексами и смыслами – семантику языка. Наибольших успехов математическая лингвистика достигла в изучении синтаксиса, где за последние 30 лет сложился специальный математический аппарат – теория формальных грамматик.

С точки зрения синтаксиса язык понимается не как средство общения, а как множество формальных объектов – последовательностей символов алфавита, которые в теории алгоритмов и формальных систем называют словами. Язык, понимаемый как множество слов, будем называть формальным языком.

Регулярные языки и грамматики

Пусть задан конечный алфавит

и тем самым множество всех конечных слов в этом алфавите:

.

Формальный язык в алфавите – это произвольное подмножество .

Набор правил образования слов формального языка называют его грамматикой. В зависимости от сложности этих правил формальные языки делятся на ряд классов. Далее мы рассмотрим один из наиболее простых классов языков – регулярные языки – и установим их связь с конечными автоматами.

Рассмотрим совокупность языков с одним и тем же алфавитом и введем операции над этими языками.

1°. Объединение. Это теоретико-множественная операция, которая, в отличие от пересечения и дополнения, имеет естественную синтаксическую интерпретацию:

.

2°. Конкатенация – это операция, связанная с подстановкой языка в язык:

.

3°. Итерация языка определяется равенством

,

где – язык, состоящий из пустого слова, который не надо смешивать с пустым языком , не содержащим ни одного слова; , , …

Языки , , состоящие из пустого или однобуквенного слова, называются элементарными.

Язык называется регулярным, если его можно построить с помощью конечного числа операций объединения, конкатенации и итерации.