Теория автоматов. 1.Формальные языки и грамматики. Классификация грамматик по Хомскому

Конечное мн-во символов, неделимых в данном рассмотрении, наз. словарем (алфавитом), а символы, входящие в множество, - буквами алфавита.

Например, алфавит A = {a, b, c, +,!} содержит 5 букв, а алфавит B = {00, 01, 10, 11} содержит 4 буквы, каждая из которых состоит из двух символов.

Последовательность букв алфавита наз. словом (цепочкой). Число букв в слове, наз. его длиной.

Пустой язык — язык порождаемый Г, не содержит ни одной конечной цепочки (конечного слова).

(ε) – пустой символ.

Грамматика (Г) [формальная] — способ описания формального языка, то есть выделения некоторого подмножества из множества всех слов некоторого конечного алфавита.

Грамматика состоит из (терминального и нетерминального алфавитов, начального символа, мн-во правил вывода)

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

Распознающие (аналитическая) Г — позволяют по данному слову определить, входит оно в язык или нет.

Терминал (терминальный алфавит - V_T) — объект, непосредственно присутствующий в словах языка, соответствующего грамматике, и имеющий конкретное, неизменяемое значение (обобщение понятия «буквы»). Обычно обозначают маленькими буквами.

Нетерминал (нетермин. Алфавит - V_N) — объект, обозначающий какую-либо сущность языка (например: формула, арифметическое выражение, команда) и не имеющий конкретного символьного значения.

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

По иерархии Хомского, грам-ки делятся на 4 типа, каждый последующий является более ограниченным подмн-вом предыдущего (но и легче поддающимся анализу).

тип0. грамматики общего вида (неограниченные): на правила вывода нет ограничений.

тип 1. контекстно-зависимые грамматики: левая часть может содержать один нетерминал, окруженный «контекстом» (последовательности символов, в том же виде присутствующие в правой части); сам нетерминал заменяется непустой последовательностью символов в правой части.

Вид: хАу → хφу, где A ∈ VN, x, y, φ ∈ (V_N ∪ V_T)⁺ Пример: S → 0A1; 0A → 00A1; A → (ε)

тип 2. контекстно-свободные грамматики (бесконтекстные): левая часть состоит из одного нетерминала.

Вид: А → φ, где А ∈ VN, φ ∈ (VN ∪ VT)*. Примеры: S → abc. S → aB; B → Cd | dc; C → (ε)

тип 3. автоматные грамматики (регулярные): более простые, эквивалентны конечным автоматам:

а) леволинейные (леворекурсивные): Вид: А → Аа | a, где А ∈ VN;

б) праволинейные (праворекурсивные): Вид: А → аA | a.

Однозначная Г — если любого слова выводимого в этой грамматике синтаксические деревья для всевозможных синтаксических разборов совпадают.

Неоднозначная: S → 0 | S+0 | 0+S S → a | aa Однозначная: S → aABc; A → cSB | Ab; B → bB | a

Неоднозначность ведёт к тому, что приоритеты операций не учитываются.

Детерменированность — однозначность.

Автоматная Г наз. Недетерминированной, если сущ. нетерминал <А>, терминал а, и как минимум два нетерминала B₁ и B₂ такие, что в грамматике есть правило: А → aB₁ | aB₂

АГ наз. Детерминированной (однозначной), если для любого А и а, сущ. ровно одно В, т.ч. есть правило:

А → аВ.

Для любой недетерминированной АГ сущ. Эквивалентная ей детерминированная АГ.