Структуры данных и модели вычислений

         

Способы задания формальных языков


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

Формальной грамматикой для порождения формального языка в алфавите называется набор

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

Правило применимо к слову , если

является фрагментом слова . Результатом применения этого правила к слову называется слово , полученное заменой любого фрагмента

в слове

на слово .

Если — результат применения некоторого правила к слову , то пишем .

Если , то пишем .

Язык , порождаемый грамматикой , определяется следующим образом:

Другими словами, — множество слов в основном алфавите, которые могут быть получены из стартового символа путем конечного числа применений правил грамматики.

Классификация Хомского:

  • Грамматики типа — это грамматики, не имеющие ограничений на вид правил.
  • Грамматики типа — это грамматики, в которых правила имеют вид , где — нетерминальный символ, а , , — слова в объединенном алфавите. Слова , называются контекстом правила. Эти грамматики (и языки, порождаемые ими) называются контекстными, так как в описанном правиле символ заменяется словом , если находится в контексте , .
  • Грамматики типа — это грамматики, в которых правила имеют вид , где — нетерминальный символ, а — непустое слово в объединенном алфавите. Эти грамматики (и языки, порождаемые ими) называются контекстно-свободными.
  • Грамматики типа — это грамматики, в которых правила имеют вид , где — нетерминальный символ, а может иметь вид либо , либо , где — символ основного алфавита, а — вспомогательного. Языки, порождаемые грамматиками типа , называются регулярными.

Известно, что класс языков, задаваемых грамматиками типа , является классом рекурсивно перечислимых языков, не совпадающим с классом рекурсивных языков. На языке теории алгоритмов это означает, что не существует алгоритма, который по любой грамматике типа 0 и любому слову отвечает на вопрос "". С другой стороны, существует алгоритм, который, получив на входе грамматику

и слово , ответит "да", если , в противном случае он либо ответит "нет", либо будет работать бесконечно.

Классы языков, задаваемых грамматиками типа , , , являются классами рекурсивных языков.

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



Содержание  Назад  Вперед