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

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

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

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

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

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

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

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

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

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

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

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

35. Конечный автомат называется автоматом Мура, если его функция выходов зависит только от состояния:

Общая модель конечного автомата, которая рассматривалась ранее, называется автоматом Милли.

Несмотря на то, что автомат Милли – частный случай автомата Мура, возможности этих двух автоматов совпадают.

Теорема. Для любого автомата Милли существует эквивалентный ему автомат Мура.

Рассмотрим автомат Мура с двумя выходными символами 0 и 1.Такой автомат будет для одних входных слов выдавать 1, для других – 0. Будем считать, что в первом случае автомат «распознал» слово, а во втором – нет. Тем самым определяется некоторый язык, состоящий из слов, распознаваемых автоматом.

Разобьем состояния автомата Мура на два класса: класс – выход равен 1, класс – выход равен 0. Это позволяет не рассматривать функцию выходов и определить автомат-распознаватель как систему