Грамота
<<  Грамматика эстонского языка Классификация грамматик и языков (классификация Хомского)  >>
Картинок нет
Картинки из презентации «Теория формальных языков и грамматик» к уроку русского языка на тему «Грамота»

Автор: Volkova. Чтобы познакомиться с картинкой полного размера, нажмите на её эскиз. Чтобы можно было использовать все картинки для урока русского языка, скачайте бесплатно презентацию «Теория формальных языков и грамматик.pptx» со всеми картинками в zip-архиве размером 93 КБ.

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

содержание презентации «Теория формальных языков и грамматик.pptx»
Сл Текст Сл Текст
1Теория формальных языков и грамматик. 6Грамматики G1 и G2 почти эквивалентны,
Определения 1. Цепочка символов в алфавите если L(G1) ? {?} = L(G2) ? {?}. Например,
V - любая конечная последовательность 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 }.
Например, если ? = ab и ? = cd, то ?? = 7Классификация грамматик и языков по
abcd, ?? = ?? = ?. Обращение (или реверс) Хомскому. ТИП 0: Грамматика G = (T, N, P,
цепочки ? - цепочка, символы которой S) - грамматика типа 0, если на ее правила
записаны в обратном порядке, обозначается вывода не накладывается никаких
как ?R. Например, если ? = abcdef, то ?R = ограничений. ТИП 1: Грамматика G = (T, N,
fedcba, ? = ?R. n-ая степенью цепочки ? P, S) - неукорачивающая грамматикой, если
(?n) – конкатенация n цепочек ?; ?0 = ?; каждое правило из P имеет вид ? ? ?, где ?
?n = ? ?n-1 = ?n-1 ?. Длина цепочки - ? (T ? N)+, ? ? (T ? N)+ и | ? | <= | ?
количество составляющих ее символов. |. Исключение - в неукорачивающей
Например, если ? = abcdefg, то длина ? грамматике допускается наличие правила S ?
равна 7. Длину цепочки ? обозначается | ? ?, при условии, что S (начальный символ)
| . | ? | = 0. не встречается в правых частях правил.
2Определения 2. Язык в алфавите V - это Грамматика G = (T, N, P, S) -
подмножество цепочек конечной длины в этом контекстно-зависимая ( КЗ ), если каждое
алфавите. V* - множество, содержащее все правило из P имеет вид ? ? ?, где ? = ?1 A
цепочки конечной длины в алфавите V, ?2; ? = ?1 ? ?2; A ? N; ? ? (T ? N)+; ?1,
включая пустую цепочку ?. Например, если V ?2 ? (T ? N)*. В КЗ-грамматике допускается
= { 0, 1 }, то V* = {?, 0, 1, 00, 11, 01, Исключение. Грамматику типа 1 можно
10, 000, 001, 011, ...}. V+ - множество, определить как неукорачивающую либо как
содержащее все цепочки конечной длины в контекстно-зависимую.
алфавите V, исключая пустую цепочку ?. V* 8Классификация грамматик и языков по
= V+ ? { ? }. Хомскому. ТИП 2: Грамматика G = (T, N, P,
3Порождающая грамматика. Порождающая S) - контекстно-свободная ( КС ), если
грамматика G - это четверка G = (T, N, P, каждое правило из Р имеет вид A ? ?, где A
S) , где T – непустое множество ? N, ? ? (T ? N)*. Грамматика G = (T, N,
терминальных символов ( алфавит терминалов P, S) - неукорачивающая
), N – непустое множество нетерминальных контекстно-свободная (НКС), если каждое
символов (алфавит нетерминалов), не правило из Р имеет вид A ? ?, где A ? N, ?
пересекающийся с T, P - конечное ? (T ? N)+. В неукорачивающей
подмножество множества (T ? N)+ ? (T ? КС-грамматике допускается Исключение.
N)*. Элемент (?, ?) множества P называется Грамматику типа 2 можно определить как
правилом вывода и записывается в виде ? ? контекстно-свободную либо как
?, причем ? содержит хотя бы один неукорачивающую контекстно-свободную. ТИП
нетерминальный символ. S - начальный 3: Грамматика G = (T, N, P, S) -
символ (цель) грамматики, S ? N. праволинейная, если каждое правило из Р
Декартовым произведением A ? B множеств A имеет вид имеет вид: A ? wB либо A ? w,
и B называется множество { (a,b) | a ? A, где A, B ? N, w ? T *. Грамматика G = (T,
b ? B}. N, P, S) - леволинейная, если каждое
4Соглашения. 1) Большие латинские буквы правило из Р имеет вид: A ? Bw либо A ? w,
будут обозначать нетерминальные символы. где A, B ? N, w ? T *. Грамматику типа 3
2) S - будет обозначать начальный символ (регулярную, Р-грамматику) можно
(цель) грамматики. 3) Маленькие греческие определить как праволинейную либо как
буквы будут обозначать цепочки символов. леволинейную. Автоматная грамматика -
4) Все остальные символы (маленькие праволинейная (леволинейная) грамматика,
латинские буквы, знаки операций и пр.) такая, что каждое правило с непустой
будем считать терминальными символами. 5) правой частью имеет вид: A ? a либо A ? aB
для записи правил вывода с одинаковыми (для леволинейной, A ? a либо A ? Ba), где
левыми частями ? ? ?1 ? ? ?2 ... ? ? ?n A, B ? N, a ? T.
будем пользоваться сокращенной записью ? ? 9Соотношения между типами грамматик.
?1 | ?2 |...| ?n. Каждое ?i , i = 1, 2, неук. Р ? неук. КС ? КЗ ? Тип 0 Любая
... ,n , будем называть альтернативой регулярная грамматика является
правила вывода из цепочки ?. Пример КС-грамматикой. Любая неукорачивающая
грамматики: G1 = ( {0,1}, {A,S}, P, S), КС-грамматика является КЗ-грамматикой. (3)
где P состоит из правил: S ? 0A1 0A ? 00A1 Любая неукорачивающая грамматика является
A ? ? грамматикой типа 0. Язык L(G) является
5Определения 3. Цепочка ? ? (T ? N)* языком типа k по Хомскому, если его можно
непосредственно выводима из цепочки ? ? (T описать грамматикой типа k, где k -
? N)+ в грамматике G = (T, N, P, S) , максимально возможный номер типа
обозначается: ? ? ? , если ? = ?1 ? ?2, ? грамматики по Хомскому. ?,
= ?1 ? ?2, где ?1, ?2, ? ? (T ? N)*, ? ? 10Соотношения между типами языков. Р ?
(T ? N)+ и правило вывода ? ? ? содержится КС ? КЗ ? Тип 0 Каждый регулярный язык
в P. Цепочка ? ? (T ? N)* выводима из является КС-языком, но существуют
цепочки ? ? (T ? N)+ в грамматике G = (T, КС-языки, которые не являются регулярными
N, P, S), обозначается ? ? ?, если ( например, L = { an bn | n > 0 }).
существуют цепочки ?0, ?1, ... , ?n (n Каждый КС-язык является КЗ-языком, но
>= 0), такие, что ? = ?0 ? ?1 ? ... ? существуют КЗ-языки, которые не являются
?n = ?. Последовательность ?0, ?1,..., ?n КС-языками ( например, L = { an bn cn | n
называется выводом длины n. Язык, > 0 }). Каждый КЗ-язык является языком
порождаемый грамматикой G = (T, N, P, S) - типа 0, но существуют языки типа 0,
L(G) = {? ? T* | S ? ?}. Сентенциальная которые не являются КЗ-языками (например:
форма в грамматике G = (T, N, P, S) - язык, состоящий из записей самоприменимых
цепочка ? ? (T ? N)*, для которой S ? ?. алгоритмов Маркова в некотором алфавите).
Язык, порождаемый грамматикой - множество (4) Кроме того, существуют языки, которые
терминальных сентенциальных форм. вообще нельзя описать с помощью
6Определения 4. Грамматики G1 и G2 порождающих грамматик. Такие языки не
называются эквивалентными, если L(G1) = являются рекурсивно перечислимым
L(G2). Например, G1 = ({0,1}, {A,S}, P1, множеством. Проблема, можно ли язык,
S) и G2 = ({0,1}, {S}, P2, S) P1: S ? 0A1 описанный грамматикой типа k, описать
P2: S ? 0S1 | 01 0A ? 00A1 A ? ? грамматикой типа k + 1 (k = 0, 1, 2),
эквивалентны, т.к. обе порождают язык является алгоритмически неразрешимой. ?,
L(G1) = L(G2) = { 0n 1n | n > 0}. 11Диаграмма Венна для классов языков.
Теория формальных языков и грамматик.pptx
http://900igr.net/kartinka/russkij-jazyk/teorija-formalnykh-jazykov-i-grammatik-236791.html
cсылка на страницу

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

другие презентации на тему «Теория формальных языков и грамматик»

«Теория возникновения жизни» - Введение. Капли были способны поглощать извне вещества по типу открытых систем. Панспермия. Учёный кипятил в воде различные среды, в которых могли бы образоваться микроорганизмы. Креационизм. Пастер присоединил к S-образной трубке запаянную колбу со свободным концом. Теория биопоэза. Споры микроорганизмов оседали на изогнутой трубке и не могли проникнуть в питательную среду.

«Теория организации» - На некоторое время эпицентр мирового обществоведения переместился в Россию. Марчу). Концепция создания организации по типу общины. Модель организационного потенциала. Основные концепции классической теории организации. Базовые постулаты современных концепций менеджмента. ТЕМА 2. Развитие теории организации.

«Теория света» - Развитие взглядов на природу света. Квантовая теория света. Как называется раздел физики, изучающий природу и свойства света? Корпускулярная теория Свет – поток фотонов. Как называется восприятие организмом света? Свет – поток определённых и неделимых порций энергии (кванты, фотоны). Что такое геометрическая оптика?

«Грамматика английского языка» - Comparative and superlative adjectives. Modal verbs. Future Continuous and Future Perfect. Comparisons. Time and condition clauses with future reference. Question tags. Грамматика английского языка. Determiners. Grammar and Vocabulary for First Certificate. Order of adjectives. English Grammar in Use Intermediate.

«Теории кислот и оснований» - в) Свободнорадикальное замещение SR. Теории кислот и оснований Классификация реакций и реагентов. Классификация органических реакций. в) Свободнорадикальное присоединение AR или AdR. Реагент – молекула, или интермедиат, которая / ый воздействует во время реакции на субстрат. Количественно кислотность и основность оценивают, как правило, по отношению к воде.

«Теории личности» - Теория черт Г. Оллпорта (G. Allport). Как психоаналитическая теория объясняет развитие личности? Низкие оценки Небрежный Ленивый Неорганизованный Непунктуальный. Низкие оценки Спокойный Пассивный Замкнутый Склонный к уединению. Добросовестность. Высокие оценки Беспокойный Неуравновешанный Стеснительный Эмоциональный.

Грамота

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

Русский язык

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