Материалы (2) (Материалы к лекциям)

22Классификация грамматик и языков по Хомскомуграмматики классифицируются по виду их правил выводаЧетыре типа грамматик:тип 0, тип 1, тип 2, тип 3Язык, порождаемый грамматикой типа k (k=0,1,2,3),является языком типа k.23G =  T, N, P, S Тип 0Любая порождающая грамматика является грамматикойтипа 0.На вид правил грамматик этого типа не накладываетсяникаких дополнительных ограничений.Класс языков типа 0 совпадает с классом рекурсивноперечислимых языков (распознаваемых МТ).24Грамматики с ограничениями на вид правил выводаТип 1Грамматика G =  T, N, P, S  называется неукорачивающей,если правая часть каждого правила из P не короче левой части(т.

е. для любого правила  →   P выполняется неравенство|  |  |  | ).В виде исключения в неукорачивающей грамматикедопускается наличие правила S → , при условии, что S(начальный символ) не встречается в правых частях правил.Грамматикой типа 1 будем называть неукорачивающуюграмматику.25Тип 1 в некоторых источниках определяют с помощью такназываемых контекстно-зависимых грамматик.Грамматика G =  T, N, P, S  называется контекстнозависимой (КЗ), если каждое правило из P имеет вид  → , где = 1A2,  = 12, A  N,   (T  N )+, 1, 2  (T  N)*.В виде исключения в КЗ-грамматике допускается наличиеправила S → , при условии, что S (начальный символ) невстречается в правых частях правил.КЗ-грамматика удовлетворяет определению неукорачивающей.Неукорачивающие и КЗ-грамматики определяют один и тот же классязыков.26Тип 2Грамматика G =  T, N, P, S  называется контекстносвободной (КС), если каждое правило из Р имеет вид A → , гдеA  N,   ( T  N ) *.В КС-грамматикахправыми частями.допускаютсяправиласпустымиЯзык, порождаемый контекстно-свободной грамматикой,называется контекстно-свободным языком.Грамматикой типа 2 будем называть контекстно-свободнуюграмматику.27Любую КС-грамматику можно преобразовать в эквивалентнуюнеукорачивающую КС-грамматику.

(т.е. КС, удовлетворяющуютакже и определению неукорачивающей)Тип 3Грамматика G =  T, N, P, S  называется праволинейной,если каждое правило из Р имеет вид A → wB либо A → w,где A  N, B  N, w  T *.Грамматика G =  T, N, P, S  называется леволинейной, есликаждое правило из Р имеет вид A → Bw либо A → w, где A  N,B  N, w  T *.28Праволинейные и леволинейные грамматики определяютодин и тот же класс языков. Такие языки называютсярегулярными.Право- и леволинейные грамматики тоженазывают регулярными.29Регулярная грамматика является грамматикой типа 3.Автоматной грамматикой называется праволинейная(леволинейная) грамматика, такая, что каждое правило снепустой правой частью имеет вид: A → a либо A → aB (длялеволинейной, соответственно, A → a либо A → Ba), где A  N,B  N, a  T.Для любой регулярной (автоматной) грамматики Gсуществуетнеукорачивающаярегулярная(автоматная)грамматика G′, такая что L(G) = L(G′).30Иерархия ХомскогоСправедливы следующие соотношения:1) любая регулярная грамматика является КС-грамматикой;2) любая неукорачивающая КС-грамматика является КЗграмматикой;3)любаянеукорачивающаяграмматикаявляетсяграмматикой типа 0.Неукорачивающие Регулярные  Неукорачивающие КС  КЗ  Тип 0(Запись A  B означает, что A является собственным подклассом класса B)31Справедливы следующие соотношения для языков: каждый регулярный язык является КС-языком, носуществуют КС-языки, которые не являются регулярными,например:L  {an bn | n > 0}; каждый КС-язык является КЗ-языком, но существуют КЗязыки, которые не являются КС-языками, например:L  {an bncn | n > 0}; каждый КЗ-язык является языком типа 0 (т.

е. рекурсивноперечислимым языком), но существуют языки типа 0,которые не являются КЗ-языками, например: язык,состоящий из записей самоприменимых алгоритмовМаркова в некотором алфавите.32Иерархия классов языковТип 3 (Регулярные)  Тип 2 (КС)  Тип 1 (КЗ)  Тип 033Проблема «Можно ли язык, описанный грамматикой типа k(k  0, 1, 2), описать грамматикой типа k + 1 ?» являетсяалгоритмически неразрешимой.Язык La,b  {a, b}. Какого он типа? Обычно требуется указатьмаксимально возможный тип.Ответ: типа 3S→a|b— грамматика типа 3, порождающая данный язык.(La,b является также языком типа 2, 1, 0 в силу иерархии Хомского).