Классификация грамматик по Хомскому

Грамматика G называется грамматикой типа 3, регулярной, праволинейной или автоматнойграмматикой(А-грамматикой), если каждое правило из R имеет вид:

A ® xA (праволинейное правило) или

A ® x (заключительное правило), где A ÎV_N, x ÎV_T.

То есть каждое правило такой грамматики содержит единственный нетерминал в левой части, всегда один терминал в правой части, за которым может следовать один нетерминал. Для таких грамматик мы в дальнейшем будем пользоваться термином автоматная (А- ) грамматика.

Грамматика G называется грамматикой типа 2, бесконтекстной или контекстно - свободной(КС- ) грамматикой если ее правила имеют вид:

A ® a, где AÎV_N, a Î (V_NÈ V_T) ^*.

То есть в каждом правиле такой грамматики имеет место единственный нетерминал слева и произвольная цепочка из терминалов и нетерминалов справа, возможно и пустая. Замена A на a в сентециальной форме не зависит от того, в каком окружении, в каком контексте находится A.

Грамматика G называется грамматикой типа 1, контекстной, нормальных составляющих(НС-) или контекстно - зависимой(КЗ- ) грамматикой, если ее правила имеют вид:

jAy ® jay, где A ÎV_N, j, y Î (V_NÈ V_T) ^* и a Î (V_NÈ V_T)⁺, то есть в каждом правиле нетерминал A в контексте j и y заменяется на непустую цепочку a в том же контексте.

Грамматика G называется грамматикойтипа 0, грамматикой с фразовой структуройили рекурсивно перечислимой грамматикой, если ее правила имеют вид:

a®b, где на левую и правую части правил не наложено никаких ограничений. “

Нетрудно заметить, что грамматики типа i одновременно являются грамматиками типа i -1. Исключение составляют укорачивающиеКС (УКС) - грамматики, то есть грамматики, содержащие аннулирующие правила типа A® e, которые не являются КЗ-грамматиками.

Язык, определяемый грамматикой типа i называется языком типа i.

Из примеров 1.2 и 1.3 следует, что языки чисел и идентификаторов являются КС-языками (тип 2).

Тот факт, что язык определяется грамматикой типа i, еще не означает, что его нельзя породить менее мощной грамматикой типа i+1. Например, КС- грамматика с правилами S®AS ç e и A ® 0 ç 1 порождает язык {0,1}^*, который конечно же можно определить А-грамматикой S ® 0S ç 1S ç 0 | 1.

Что можно сказать о выделенных классах грамматик и языков в целом? Идеальной с теоретической и практической точек зрения являются А-грамматики и языки. Но их класс слишком узок. Даже язык арифметических выражений не является A язы­ком. Тем не менее, теория автоматных языков повсеместно используется при построении трансляторов. Класс языков типа 0, напротив, очень широк и неразрешим в общем случае. Все остальные языки (тип 1 - тип 3), которые обобщенно называют контекстными, разрешимы. Для них существуют алгоритмы, определяющие принадлежность или непринадлежность цепочек языку за конечное число шагов.

Теорема 1.1.Любой контекстный язык разрешим.

Доказательство.Для любого контекстного языка L существует порождающая его грамматика G в удлиняющей форме, у которой для всех правил вывода a®bвыполняется условие ça ½<çb ÷. (Доказательство этого факта будет дано позже). В общем случае для контекстной грамматики без аннулирующих правил выполняется условие ça÷ £ çb÷. Возьмем анализируемую терминальную цепочку h. Длина исследуемой цепочки должна быть конечной. Тогда если h Î L,то существует вывод S = x₁ Þ x₂ Þ ... Þ x _n-1 Þ x _n = h, то есть вывод S Þⁿ h, где çh÷ ³ n, так как каждый шаг вывода удлиняет цепочку не менее, чем на единицу. Число выводов с длиной не более n конечно. Поэтому достаточно проверить выводится ли h одним из них. Если h совпадает с одной из терминальных цепочек, выводимых по заданной грамматике G, не более чем за n шагов, то h Î L(G), если нет - h Ï L(G). ™

Неразрешимость языков типа 0 выводят их из рассмотрения в данном курсе,- нет смысла изучать языки, для которых невозможно определить принадлежность цепочки. Прочие же языки, как следует из теоремы 1.1, могут представлять практический интерес. В дальнейшем мы подробно рассмотрим теорию А - и КС - языков, нашедших широкое распространение при проектировании трансляторов.