Автоматы и грамматики

Основные определения. Конечный алфавит A = {a,b,c,...,x} – терминальный алфавит (малые латинские буквы).

A_* = {a,b,c,...,x}_* – все слова, полученные из букв алфавита, _* – операция итерации приписывания (конкатенации). Например, слово α = aabcc получено из α приписыванием буквы a к букве a – β = a · a, далее α = β · b· c · c получено последовательным приписыванием к слову β букв b, c, c.

L ⊆ A_* – язык, вообще говоря, состоит из бесконечного числа слов. Возникает проблема описания языка при помощи конечных и конструктивных объектов (например, формул или правил порождения).

Как обычно, рассматриваются две основные задачи.

Порождение языка L. Для порождения слова служит специальная конструкция – порождающая грамматика G, которая представляет собой конечный набор продукций (правил подстановок) для вывода любых слов языка из специального символа S (аксиомы) и только их.

Формально – G =〈A,V,P,S, A〉 – основной алфавит, V – вспомогательный алфавит, S ∈ V – аксиома, Σ =(A∪V) – объединённый алфавит, A⋂V = φ, P –правила (подстановки, продукции): имеет вид σ_i→σ_j, где σ_i → σ_j∈ (Σ)_* (в общем случае) (слова в объединённом алфавите).

Распознавание слов языка L. Дано слово ω, определить ω ∈ L или ω ∉ L. Для решения этой задачи служат распознающие автоматы. Формально автомат определяется – A = 〈〉, где A – основной алфавит, S – алфавит состояний, P – правила вида s_i · w_i→ S_j, w_i∈A_*, s_i,s_j∈S.