Структуры данных и модели вычислений
Способы задания формальных языков
Прежде всего, для задания формального языка может подойти любое математически корректное определение множества слов в заданном алфавите. Однако если иметь в виду задание, при котором возможно алгоритмическое решение вопроса о принадлежности слова языку, то нужны средства более ограниченные. Наиболее общим из конструктивных способов задания языков является способ, использующий так называемые формальные грамматики.
Формальной грамматикой для порождения формального языка в алфавите называется набор
где — алфавит терминальных (основных) символов; — алфавит нетерминальных (вспомогательных) символов, ; — стартовый символ, ; — конечный набор правил вывода. Каждое правило вывода имеет вид , где , — слова в объединенном алфавите , причем содержит хотя бы один символ из алфавита .
Правило применимо к слову , если
является фрагментом слова . Результатом применения этого правила к слову называется слово , полученное заменой любого фрагмента
в слове
на слово .
Если — результат применения некоторого правила к слову , то пишем .
Если , то пишем .
Язык , порождаемый грамматикой , определяется следующим образом:
Другими словами, — множество слов в основном алфавите, которые могут быть получены из стартового символа путем конечного числа применений правил грамматики.
Классификация Хомского:
- Грамматики типа — это грамматики, не имеющие ограничений на вид правил.
- Грамматики типа — это грамматики, в которых правила имеют вид , где — нетерминальный символ, а , , — слова в объединенном алфавите. Слова , называются контекстом правила. Эти грамматики (и языки, порождаемые ими) называются контекстными, так как в описанном правиле символ заменяется словом , если находится в контексте , .
- Грамматики типа — это грамматики, в которых правила имеют вид , где — нетерминальный символ, а — непустое слово в объединенном алфавите. Эти грамматики (и языки, порождаемые ими) называются контекстно-свободными.
- Грамматики типа — это грамматики, в которых правила имеют вид , где — нетерминальный символ, а может иметь вид либо , либо , где — символ основного алфавита, а — вспомогательного. Языки, порождаемые грамматиками типа , называются регулярными.
Известно, что класс языков, задаваемых грамматиками типа , является классом рекурсивно перечислимых языков, не совпадающим с классом рекурсивных языков. На языке теории алгоритмов это означает, что не существует алгоритма, который по любой грамматике типа 0 и любому слову отвечает на вопрос "". С другой стороны, существует алгоритм, который, получив на входе грамматику
и слово , ответит "да", если , в противном случае он либо ответит "нет", либо будет работать бесконечно.
Классы языков, задаваемых грамматиками типа , , , являются классами рекурсивных языков.
Альтернативный способ задания формальных языков — их описание с помощью различных видов автоматов. Одним из простейших классов языков, имеющих большое прикладное значение, является класс регулярных языков, допускающих описание и с помощью конечных автоматов, и с помощью аналитических выражений.
