Метод был ранее определен как алфавитный оператор с конечной системой правил преобразования. Для записи входных, промежуточные и выходных слов употребляется некий алфавит. Каким-то образом должны быть описаны и правила преобразования. Разумеется, для этого требуется некий язык. Подходящие ли для описания метода обыденный разговорный язык?

Хоть какой естественный язык появлялся как средство общения людей. Конкретно по этой причине ему присущи такие особенности как:

• изменчивость, которая состоит в непостоянстве словарного состава языка;
• неоднозначность трактовки фраз разными людьми;
• избыточность, о чем шла речь в главе «Кодирование символьной информации».

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

В любом языке — естественном либо искусственном — можно выделить две составляющие: синтаксис и семантику. Синтаксис (грамматика языка) — это совокупность правил, согласно которым строятся допустимые в данном языке конструкции. Семантика — смысловая сторона языка — она соотносит единицы и конструкции языка с неким наружным миром, для описания которого язык употребляется.

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

Неважно какая грамматика начинается с указания алфавита, т.е. набора знаков, средством которого строятся конструкции языка.

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

Кроме синтаксиса устанавливается система правил, позволяющих конструкциям языка придать смысл — эти правила образуют семантику языка.

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

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

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

Формальная грамматика задается упорядоченной четверкой {T, N, S, Р}, где Т и N — не пересекающиеся конечные огромного количества, образующие алфавит либо словарь порождаемого формального языка; Т именуется обилием (словарем) терминальных знаков; N — обилием (словарем) не терминальных (вспомогательных) знаков. S — исходный (выделенный) вспомогательный знак из огромного количества N. Р — набор правил вывода конструкций языка (подстановок) из выделенного вспомогательного знака, имеющие вид g→ h, где g и h — цепочки, состоящие как из терминальных, так и нетерминальных знаков.

Подстановки работают последующим образом: если в преобразуемой цепочке есть слово g, то оно заменяется словом h. Единственное ограничение с виду подстановок заключается в том, что слово g не может состоять только из терминальных знаков. Это значит, что получение на неком шаге цепочки, состоящей только из терминальных знаков, свидетельствует о прекращении процесса порождения — эта цепочка является правильной, завершенной конструкцией порождаемого языка. Подстановки Р могут применяться к трансформируемой цепочке в случайном порядке.