Операции над языками. 
Регулярные выражения

L M = {s | s L s M}.

LM = { append (s1, s2) | s1 L s2 M}.

L0 L1 L2 … L* =? i=0 Li.

L⁺ = ^? _i=1 Lⁱ

Формальные языки можно определить, пользуясь регулярными выражениями. С их помощью можно показать, как строятся элементы языка. Регулярные выражения над алфавитом определяются индуктивно.

Регулярное множество в алфавите T определяется рекурсивно следующим образом:

• 1. (пустое множество)? регулярное множество в алфавите T;
• 2. {e}? регулярное множество в алфавите T (e? пустая цепочка);
• 3. {a}? регулярное множество в алфавите T для каждого ;
• 4. если P и Q? регулярные множества в алфавите T, то регулярными являются и множества
• 1. p|q
• 2. pq
• 3. p*
• 5. ничто другое не является регулярным множеством в алфавите T.

Итак, множество в алфавите T регулярно тогда и только тогда, когда оно либо, либо {e}, либо {a} для некоторого, либо его можно получить из этих множеств применением конечного числа операций объединения, конкатенации и итерации.

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

НКА: формальное описание, построение множества достижимых состояний

Цепочка принимается автоматом, если существует путь из начального состояния в конечное, метки дуг которого формируют эту цепочку.

Формально КА определяется пятеркой ₀, F>,

S — конечное множество состояний;

— конечное множество входных символов (алфавит);

— отношение переходов, это подмножество S на У, к которому добавлена пустая строка; s Ч ({})Чs

s0 — начальное состояние; s0 S

F S — множество финальных состояний.

Функция переходов — определяет для заданного состояния s и входной последовательности w множество состояний, в которых может оказаться автомат, обработав входную строку w. Определяется:

• 1) s' (S,) если s' (s,)
• 2) s' (S,) если есть путь по переходам, т. е. если есть состояние s'' (S,) и одновременно s' (s'',)
• 3) когда строка не пустая: s' (S, aw), если есть состояние s'' (s, а) и s' (s'', w). Работа конечного автомата представляет собой некоторую последовательность шагов, или тактов. Такт определяется текущим состоянием управляющего устройства и входным символом, обозреваемым в данный момент входной головкой. Сам шаг состоит из изменения состояния и, возможно, сдвига входной головки на одну ячейку вправо.

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