Формальный язык

Материал из WikiGrapp
Перейти к:навигация, поиск

Формальный язык (Formal language) — произвольное множество \,L цепочек в некотором заданном алфавите \,\Sigma, т.е. L \subseteq \Sigma^*.

Так как язык — это множество, то операции объединения,пересечения, нахождения разности и дополнения применимы и к языкам. Кроме того, различные операции, определенные для цепочек, применяются и к языкам (например, L^R = \{\alpha^R : \alpha \in L\}). Среди основных из них — операции конкатенации и итерации.

Язык \,L_1 L_2, называемый конкатенацией (а также сцеплением или произведением) языков \,L_1 и \,L_2, — это язык

\{\alpha\beta: \alpha \in L_1 и  \beta \in L_2\}.

Итерация языка \,L, обозначаемая через \,L^*, определяется по следующим правилам:

(1) \, L^o = \{e\};

(2)  \,L^n = LL^{n-1} для  n \geq 1;

(3)  L^* = \bigcup\limits_{n\geq O} L^n.

Позитивная итерация языка \,L, обозначаемая через \,L^+, — это язык \bigcup\limits_{n\geq 1} L^n. Заметим, что \,L^+=LL^*=L^*L и \,L^*=L^+\cup\{e\}.

Если язык \,L состоит из небольшого числа цепочек, то самый очевидный способ описания языка — составить список всех цепочек из \,L. Однако многие языки (например, языки программирования) невозможно или нежелательно задавать исчерпывающим перечислением входящих в них цепочек, и поэтому, как правило, используются другие способы определения языка. Причем используются только такие способы, которые позволяют описанию языка быть обозримым (заведомо конечным), хотя описываемый язык может быть и бесконечным. Известно несколько методов определения языка, удовлетворяющих этому требованию.

Один из них связан со способом задания множества с помощью характеристического свойства (предиката) и состоит в использовании частичного алгоритма (предписания производить некоторые действия), который для произвольной входной цепочки остановится и ответит "да" после конечного числа шагов, если эта цепочка принадлежит языку. Схематизированные устройства, используемые для представления таких алгоритмов, получили название распознавателей. Примерами распознавателей являются конечные автоматы, автоматы с магазинной памятью и машины Тьюринга.

Второй метод описания языка имеет вид исчисления, называемого грамматикой, — некоторой порождающей системы (разрешения производить некоторые действия), используя которую можно получить (породить) все цепочки языка \,L и только их. Одно из преимуществ определения языка с помощью грамматики состоит в том, что грамматика придает цепочкам ("предложениям") языка полезную структуру, которая может использоваться, например, для придания смысла предложениям языка.

Язык \,L называется автоматным, праволинейным, регулярным, контекстно-свободным, контекстно-зависимым и т.д., если существует грамматика \,G соответствующего типа, которая порождает этот язык, т.е. для которой \,L(G)=L.

Литература

  • Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. — М.: Мир, 1978. — Т. 1,2.
  • Бауэр Ф.Л., Гооз Г. Информатика. — М: Мир, 1990. — Т. 1,2.
  • Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995.
  • Касьянов В.Н., Поттосин И.В. Методы построения трансляторов. — Новосибирск: Наука. Сиб. отд-ние, 1986..