Определение.

К порождающим относятся грамматики языка L, по которым можно построить любую «правильную» цепочку с указанием ее структуры и нельзя построить ни одной неправильной цепочки.

Определение.

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

Распознающая грамматика задает критерий принадлежности произвольной цепочки данному языку.

Формальные грамматики широко применяются в лингвистике и программировании в связи с изучением естественных языков и языков программирования.

Автоматные и лингвистические модели строятся на базе теории формальных грамматик, основы которой были заложены в работах лингвиста Н. Хомского.

Определение.

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

Символы будем обозначать строчными буквами латинского алфавита, а цепочки – в виде «ffghhh», которые будем считать ориентированными слева направо.

Цепочки будем обозначать также специальными символами – прописными буквами латинского алфавита или греческими буквами, например: γ = ffg, В = аbbа.

Определение.

Пустая цепочка ε это цепочка, которая не содержит ни одного символа.

Определение.

Длиной цепочки будем называть число символов, входящих в эту цепочку.

Длина цепочки обозначается следующим образом:

|γ| = | ffg | = 3;

|В| = | аbbа| = 4;

|ε| = 0.

2. Основные операции формальных грамматик.

Определение.

Конкатенацией двух цепочек Х и Y называется такая цепочка Z, которая получается непосредственным слиянием цепочки Х, стоящей слева, и цепочки Y, стоящей права.

Например, если X = ffg, Y = ghh, то конкатенация Х и Y – это цепочка Z = ffgghh. Обозначим операцию конкатенации символом о (или “.”).

Свойства операции конкатенации можно записать следующим образом:

1) свойство замкнутости:

о: А* × А* → А*;

2) свойство ассоциативности:

(∀Х ∈ А*, Y ∈ A*, Z ∈ A*)

[(X o Y) o Z = X o (Y o Z)],

где через А* обозначено множество всех возможных цепочек (разумеется, бесконечное), составленных из конечного множества А базовых элементов (символов) словаря, включая пустую цепочку ε; символ х обозначает операцию декартова произведения двух множеств; а X, Y, Z – произвольные цепочки, принадлежащие А*.

Рассмотрим пару (А*, 0). С учетом перечисленных свойств операции о эта пара представляет собой полугруппу с единичным элементом ε или моноид.

Определение.

Полугруппой в алгебре называют только множество (в данном случае А*), снабженное всюду определенной ассоциативной операцией.

Определение группы.

Пусть задано множество элементов G  g1, g2, ... , gn , обладающих следующими свойствами:

1. Определен закон умножения элементов gi gj  =  gk, причем если g_i, g_j ∈G, то g_i g_j = g_k ∈G,  i, j, l = 1, 2, ..., n.

2. Выполняется закон ассоциативности g_i (g_j g_k) = (g_i g_j) g_k.

3. Существует единичный элемент e, eg_i = g_i, i = 1, 2, ... , n.

4. Существует обратный элемент  g _i^-1, g _i^-1g_i = e,  i = 1, 2, ... , n.

Тогда на множестве G задана группа элементов g₁, g₂, ... , g_n

Цепочка может принадлежать или не принадлежать языку L.