Формальная порождающая грамматика

Date: 2015-10-07; view: 476.

Язык.

Цепочка.

Алфавит

Конечное множество символов, неделимых в данном рассмотрении, называется алфавитом (словарем), а символы, входящие во множество, называются буквами алфавита.

Конечная последовательность символов (букв) алфавита называетсяцепочкой (словом) в этом алфавите.

Пустая цепочка – цепочка, которая не содержит ни одного символа (для обозначения используется символы ε или $).

Длина цепочки (слова) – число символов (букв), входящих в цепочку. Например, слово a=ab+!c в алфавите A имеет длину l(a)=5 или |а|=5; слово b=00110010 в алфавите B имеет длину l(b)=4; если α=abcdefg, то длина α равна 7: l(α)=7 или |α|=7; длина пустой цепочки ε равна 0: l(ε)=0 или |ε|=0.

Конкатенация (сцепление) цепочек – это цепочка αβ, если α и β – цепочки. Например, если α=ab и β=cd, то αβ=abcd. Для любой цепочки α всегда αε=εα=α.

Обращение (реверс) цепочки α – это цепочка α^R, символы которой записаны в обратном порядке. Например, если α=abcdef, то α^R=fedcba. Для пустой цепочки: ε=ε^R.

Cтепень цепочки α – это конкатенация n цепочек α: α⁰=ε; αⁿ=αα^n-1=α^n-1α.

Язык в некотором алфавите – это подмножество цепочек конечной длины в этом алфавите. Если задан алфавит A, то существует A^* – множество всевозможных цепочек, которые могут быть построены из букв алфавита A; предполагается, что пустая цепочка (ε или $) также входит в множество A^*.

Пусть V^* – множество, содержащее все цепочки в алфавите V, включая пустую цепочку ε, тогда, если V={0,1}, то V^*={ε,0,1,00,11,01,10,000,001,011,...}.

Таким образом, каждый язык в алфавите V является подмножеством множества V^*.

Формальная грамматика (грамматика) в теории формальных языков – это способ описания формального языка, т.е. выделения некоторого подмножества из множества всех слов некоторого конечного алфавита.

Различают порождающие и распознающие (аналитические) грамматики.

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