Материалы (2) (1115029)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

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 в силу иерархии Хомского).

Характеристики

Тип файла PDF

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

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов учебной работы