Способы описания языков

Конечный язык можно описать простым перечислением его цепочек.

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

Можно выделить два основных подхода для такого представления: механизм распознавания и механизм порождения (генерации).

Механизм распознавания (распознаватель), по сути, является процедурой специального вида, которая по заданной цепочке определяет, принадлежит ли она языку. Если принадлежит, то процедура останавливается с ответом «да», т. е. допускает цепочку; иначе – останавливается с ответом «нет» или зацикливается. Язык, определяемый распознавателем – это множество всех цепочек, которые он допускает.

Примеры распознавателей:

· Машина Тьюринга (МТ). Язык, который можно задать с помощью МТ, называется рекурсивно перечислимым. Вместо МТ можно использовать эквивалентные алгоритмические схемы: нормальный алгоритм Маркова (НАМ), машину Поста и др.

· Линейно ограниченный автомат (ЛОА). Представляет собой МТ, в которой лента не бесконечна, а ограничена длиной входного слова. Определяет контекстно-зависимые языки.

· Автомат с магазинной (внешней) памятью (МП-автомат). В отличие от ЛОА, головка не может изменять входное слово и не может сдвигаться влево; имеется дополнительная бесконечная память (магазин, или стек), работающая по дисциплине LIFO. Определяет контекстно-свободные языки.

· Конечный автомат (КА). Отличается от МП-автомата отсутствием магазина. Определяет регулярные языки.

Основной способ реализации механизма порождения — использование порождающих грамматик, которые иногда называют грамматиками Хомского. Порождающие ФГ являются наиболее важными и распространенными.

Порождающей ФГ называется четверка вида: G = (VT,VN,P,S),

где VN - конечное множество нетерминальных символов грамматики (обычно прописные латинские буквы);

VT - множество терминальных символов грамматики (обычно строчные латинские буквы, цифры, и т.п.), VT Ç VN = 0;

Р - множество правил вывода грамматики; элемент (α,β) множества Р называется правилом вывода и записывается в виде α→β (читается: «из цепочки α выводится цепочка β»)

S - начальный символ грамматики, S Î VN.

Для записи правил вывода с одинаковыми левыми частями вида α→β1, α→β2,…,α→βn используется сокращенная форма записи α→β1|β2|…|βn.

Пример. Грамматика G 1 = ({0, 1}, {A, S}, Р1, S), где множество Р1 состоит из правил вида: 1) S→0A1; 2) 0А→00А1; 3)А→ e.

Опр. Цепочка βÎ (VT È VN)* непосредственно выводима из цепочки αÎ (VT È VN)+ в грамматике G = (VT,VN,P,S) (обозначается: αÞβ ), если α=ξ1γξ2 и β=ξ1δξ2, где ξ1,ξ2,δ Î V*, γÎV+ и правило вывода γ→δ содержится во множестве Р.

Опр. Цепочка βÎ V* выводима из цепочки αÎ V+ в грамматике G =(VT,VN,P,S) (обозначается: αÞ*β ), если существует последовательность цепочек γ0,γ1,…,γn (n≥0) такая, что α=γ0Þγ1Þ…Þγn=β.

Пример. В грамматике G1 S=>*000111, т.к. существует вывод S => 0А1=> 00А11 => 000A111 => 000111.

Опр. Языком, порожденным грамматикой G = (VT, VN,P,S),называется множество всех цепочек в алфавите VT, которые выводимы из начального символа грамматики S с помощью правил множества Р, т.е. множество L(G)= {α Î V* |S Þ *α}.

Пример. Для грамматики G1 L(G1)={0 ⁿ 1 ⁿ | п>0}.

Опр. Цепочка αÎV *, для которой существует вывод S Þ *α, называется сентенциальной формой в грамматике G = (VT, VN,P, S).

Опр. Грамматики G1 и G2 называются эквивалентными, если L(G1) =L(G2).

Пример. Для грамматики G1 эквивалентной будет грамматика G2 = ({0, 1}, {S}, Р2, S), где множество правил вывода Р2 содержит правила вида S→0S1|01.