Лекции (16) (1119487)

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

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

Теория формальных языков и грамматик. Определения 1.Цепочка символов в алфавите V - любая конечная последовательностьсимволов этого алфавита.Пустая цепочка (  ) - цепочка, которая не содержит ни одного символа.Если  и  - цепочки, то цепочка  - конкатенация цепочек  и .Например, если = ab и  = cd, =  = .то = abcd,Обращение (или реверс) цепочки  - цепочка, символы которой записаны вобратном порядке, обозначается как R.Например, если = abcdef,то R = fedcba, = R.n-ая степенью цепочки  (n) – конкатенация n цепочек ;0 = ;n =  n-1 = n-1 .Длина цепочки - количество составляющих ее символов.Например, если  = abcdefg, то длина  равна 7.Длину цепочки  обозначается |  | . |  | = 0Определения 2.Язык в алфавите V - это подмножество цепочекконечной длины в этом алфавите.V* - множество, содержащее все цепочки конечнойдлины в алфавите V, включая пустую цепочку .Например, если V = { 0, 1 }, тоV* = {, 0, 1, 00, 11, 01, 10, 000, 001, 011, ...}.V+ - множество, содержащее все цепочки конечнойдлины в алфавите V, исключая пустую цепочку .V* = V+  {  }.Порождающая грамматикаПорождающая грамматика G - это четверкаG = (T, N, P, S) ,гдеT – непустое множество терминальных символов( алфавит терминалов ),N – непустое множество нетерминальных символов(алфавит нетерминалов), не пересекающийся с T,P - конечное подмножество множества (T  N)+  (T  N)*.Элемент (, ) множества P называется правилом вывода изаписывается в виде → ,причем  содержит хотя бы один нетерминальный символ.S - начальный символ (цель) грамматики, S  N.Декартовым произведением A  B множеств A и B называетсямножество { (a,b) | a  A, b  B}.Соглашения1) Большие латинские буквы будут обозначать нетерминальные символы.2) S - будет обозначать начальный символ (цель) грамматики.3) Маленькие греческие буквы будут обозначать цепочки символов.4) Все остальные символы (маленькие латинские буквы, знаки операций и пр.)будем считать терминальными символами.5) для записи правил вывода с одинаковыми левыми частями  1  2 ...

  nбудем пользоваться сокращенной записью  1 | 2 |...| n.Каждое i , i = 1, 2, ... ,n , будем называть альтернативой правила вывода изцепочки .Пример грамматики:G1 = ( {0,1}, {A,S}, P, S), где P состоит из правил:S  0A10A  00A1A Определения 3.Цепочка   (T  N)* непосредственно выводима из цепочки   (T  N)+ вграмматике G = (T, N, P, S) , обозначается:    ,если  = 1  2,  = 1  2, где 1, 2,   (T  N)*,   (T  N)+и правило вывода    содержится в P.Цепочка   (T  N)* выводима из цепочки   (T  N)+ в грамматикеG = (T, N, P, S), обозначается   ,если существуют цепочки 0, 1, ... , n (n >= 0), такие, что = 0  1  ...  n = .Последовательность 0, 1,..., n называется выводом длины n.Язык, порождаемый грамматикой G = (T, N, P, S) - L(G) = {  T* | S  }.Сентенциальная форма в грамматике G = (T, N, P, S) - цепочка   (T  N)*,для которой S  .Язык, порождаемый грамматикой - множество терминальныхсентенциальных форм.Определения 4.Грамматики G1 и G2 называются эквивалентными,если L(G1) = L(G2).Например,G1 = ({0,1}, {A,S}, P1, S)иG2 = ({0,1}, {S}, P2, S)P1: S  0A1P2: S  0S1 | 010A  00A1Aэквивалентны, т.к.

обе порождают язык L(G1) = L(G2) = { 0n 1n | n > 0}.Грамматики G1 и G2 почти эквивалентны,если L(G1)  {} = L(G2)  {}.Например,G1 = ( {0,1}, {A,S}, P1, S )P1: S  0A10A  00A1A почти эквивалентны, так какL(G1) = { 0n 1n | n > 0 }, аиG2 = ( {0,1}, {S}, P2, S )P2: S  0S1 | L(G2) = { 0n 1n | n >= 0 }.Классификация грамматик и языков по ХомскомуТИП 0:Грамматика G = (T, N, P, S) - грамматика типа 0, если на ее правила вывода ненакладывается никаких ограничений.ТИП 1:Грамматика G = (T, N, P, S) - неукорачивающая грамматикой, если каждоеправило из P имеет вид → , где   (T  N)+,   (T  N)+ и |  | <= |  |.Исключение - в неукорачивающей грамматике допускается наличие правилаS → , при условии, что S (начальный символ) не встречается в правыхчастях правил.Грамматика G = (T, N, P, S) - контекстно-зависимая ( КЗ ), если каждоеправило из P имеет вид → , где  = 1 A 2;  = 1  2; A  N;   (T  N)+; 1, 2  (T  N)*.В КЗ-грамматике допускается Исключение.Грамматику типа 1 можно определить как неукорачивающую либо какконтекстно-зависимую.Классификация грамматик и языков по ХомскомуТИП 2:Грамматика G = (T, N, P, S) - контекстно-свободная ( КС ), если каждоеправило из Р имеет вид A → , где A  N,   (T  N)*.Грамматика G = (T, N, P, S) - неукорачивающая контекстно-свободная(НКС), если каждое правило из Р имеет вид A → , где A  N,   (T  N)+.В неукорачивающей КС-грамматике допускается Исключение.Грамматику типа 2 можно определить как контекстно-свободную либо какнеукорачивающую контекстно-свободную.ТИП 3:Грамматика G = (T, N, P, S) - праволинейная, если каждое правило из Р имеетвид имеет вид: A → wB либо A → w, где A, B  N, w  T *.Грамматика G = (T, N, P, S) - леволинейная, если каждое правило из Р имеетвид: A → Bw либо A → w, где A, B  N, w  T *.Грамматику типа 3 (регулярную, Р-грамматику) можно определить какправолинейную либо как леволинейную.Автоматная грамматика - праволинейная (леволинейная) грамматика, такая,что каждое правило с непустой правой частью имеет вид: A → a либо A → aB(для леволинейной, A → a либо A → Ba), где A, B  N, a  T.Соотношения между типами грамматикнеук.

Р  неук. КС  КЗ  Тип 0(1) Любая регулярная грамматика является КСграмматикой.(2) Любая неукорачивающая КС-грамматика является КЗ,грамматикой.(3) Любая неукорачивающая грамматика являетсяграмматикой типа 0.Язык L(G) является языком типа k по Хомскому, если егоможно описать грамматикой типа k, где k - максимальновозможный номер типа грамматики по Хомскому.Соотношения между типами языковР  КС  КЗ  Тип 0(1) Каждый регулярный язык является КС-языком, но существуют КСязыки, которые не являются регулярными( например, L = { an bn | n > 0 }).(2) Каждый КС-язык является КЗ-языком, но существуют КЗ-языки,которые не являются КС-языками( например, L = { an bn cn | n > 0 }).(3) Каждый КЗ-язык является языком, типа 0, но существуют языки типа0, которые не являются КЗ-языками(например: язык, состоящий из записей самоприменимыхалгоритмов Маркова в некотором алфавите).(4) Кроме того, существуют языки, которые вообще нельзя описать спомощью порождающих грамматик.

Такие языки не являютсярекурсивно перечислимым множеством.Проблема, можно ли язык, описанный грамматикой типа k, описатьграмматикой типа k + 1 (k = 0, 1, 2), является алгоритмическинеразрешимой.Диаграмма Венна для классов языков.

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

Тип файла PDF

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

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

Список файлов лекций