Грамота
<<  Грамматика эстонского языка Классификация грамматик и языков (классификация Хомского)  >>
Теория формальных языков и грамматик
Теория формальных языков и грамматик
Определения 2
Определения 2
Порождающая грамматика
Порождающая грамматика
Соглашения
Соглашения
Определения 3. Цепочка
Определения 3. Цепочка
Определения 4. Грамматики G1 и G2 называются эквивалентными, если
Определения 4. Грамматики G1 и G2 называются эквивалентными, если
Классификация грамматик и языков по Хомскому
Классификация грамматик и языков по Хомскому
Классификация грамматик и языков по Хомскому
Классификация грамматик и языков по Хомскому
Соотношения между типами грамматик
Соотношения между типами грамматик
Соотношения между типами языков
Соотношения между типами языков
Диаграмма Венна для классов языков
Диаграмма Венна для классов языков

Презентация: «Теория формальных языков и грамматик». Автор: Volkova. Файл: «Теория формальных языков и грамматик.pptx». Размер zip-архива: 93 КБ.

Теория формальных языков и грамматик

содержание презентации «Теория формальных языков и грамматик.pptx»
СлайдТекст
1 Теория формальных языков и грамматик

Теория формальных языков и грамматик

Определения 1.

Цепочка символов в алфавите V - любая конечная последовательность символов этого алфавита. Пустая цепочка ( ? ) - цепочка, которая не содержит ни одного символа. Если ? и ? - цепочки, то цепочка ?? - конкатенация цепочек ? и ?. Например, если ? = ab и ? = cd, то ?? = abcd, ?? = ?? = ?. Обращение (или реверс) цепочки ? - цепочка, символы которой записаны в обратном порядке, обозначается как ?R. Например, если ? = abcdef, то ?R = fedcba, ? = ?R. n-ая степенью цепочки ? (?n) – конкатенация n цепочек ?; ?0 = ?; ?n = ? ?n-1 = ?n-1 ?. Длина цепочки - количество составляющих ее символов. Например, если ? = abcdefg, то длина ? равна 7. Длину цепочки ? обозначается | ? | . | ? | = 0

2 Определения 2

Определения 2

Язык в алфавите V - это подмножество цепочек конечной длины в этом алфавите. V* - множество, содержащее все цепочки конечной длины в алфавите V, включая пустую цепочку ?. Например, если V = { 0, 1 }, то V* = {?, 0, 1, 00, 11, 01, 10, 000, 001, 011, ...}. V+ - множество, содержащее все цепочки конечной длины в алфавите V, исключая пустую цепочку ?. V* = V+ ? { ? }.

3 Порождающая грамматика

Порождающая грамматика

Порождающая грамматика 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}.

4 Соглашения

Соглашения

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 ? 0A1 0A ? 00A1 A ? ?

5 Определения 3. Цепочка

Определения 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 ? ?. Язык, порождаемый грамматикой - множество терминальных сентенциальных форм.

6 Определения 4. Грамматики G1 и G2 называются эквивалентными, если

Определения 4. Грамматики G1 и G2 называются эквивалентными, если

L(G1) = L(G2). Например, G1 = ({0,1}, {A,S}, P1, S) и G2 = ({0,1}, {S}, P2, S) P1: S ? 0A1 P2: S ? 0S1 | 01 0A ? 00A1 A ? ? эквивалентны, т.к. обе порождают язык L(G1) = L(G2) = { 0n 1n | n > 0}. Грамматики G1 и G2 почти эквивалентны, если L(G1) ? {?} = L(G2) ? {?}. Например, G1 = ( {0,1}, {A,S}, P1, S ) и G2 = ( {0,1}, {S}, P2, S ) P1: S ? 0A1 P2: S ? 0S1 | ? 0A ? 00A1 A ? ? почти эквивалентны, так как L(G1) = { 0n 1n | n > 0 }, а L(G2) = { 0n 1n | n >= 0 }.

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

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

ТИП 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 можно определить как неукорачивающую либо как контекстно-зависимую.

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

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

ТИП 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.

9 Соотношения между типами грамматик

Соотношения между типами грамматик

неук. Р ? неук. КС ? КЗ ? Тип 0 Любая регулярная грамматика является КС-грамматикой. Любая неукорачивающая КС-грамматика является КЗ-грамматикой. (3) Любая неукорачивающая грамматика является грамматикой типа 0. Язык L(G) является языком типа k по Хомскому, если его можно описать грамматикой типа k, где k - максимально возможный номер типа грамматики по Хомскому.

?,

10 Соотношения между типами языков

Соотношения между типами языков

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

?,

11 Диаграмма Венна для классов языков

Диаграмма Венна для классов языков

«Теория формальных языков и грамматик»
http://900igr.net/prezentacija/russkij-jazyk/teorija-formalnykh-jazykov-i-grammatik-236791.html
cсылка на страницу

Грамота

11 презентаций о грамоте
Урок

Русский язык

100 тем
Слайды
900igr.net > Презентации по русскому языку > Грамота > Теория формальных языков и грамматик