Шпаргалка по предмету "Математическая логика"

Узнать цену работы по вашей теме


Формальные грамматики типа 0 и 1. Вывод цепочек терминальных символов.

Грамматика типа 0 - грамматика произвольного типа без каких-либо ограничений на цепочки символов. Продукции этой грамматики имеют вид: α ::= β. В обеих частях продукции могут быть в произвольном порядке и любом количестве терминальные и нетерминальные символы, т. е. α, β  V*. Такой тип грамматики порождает множество перечислимых языков, для которых существует перечисляющий алгоритм. Такой алгоритм может быть реализован на машине Тьюринга, являющейся классической моделью рекурсивной функции. Поэтому такие языки называют также рекурсивно- перечислимыми. Однако такой тип грамматики не нашел применения в языках программирования. Пример. Пусть дана грамматика G1 = , где VT = {alb}; VN = {A; B; C; J};Р ={р1: J ::= AbBb; р2: Ab ::= Bba; р3: Bb ::= Cba; р4: Cb ::= ba}. Какие цепочки терминальных символов формирует грамматика?К цепочке символов AbBb, заданной начальным символом J. можно применить два правила (Ab ::= Bba и Bb ::= Cba) и организовать два вывода: левосторонний и правосторонний. Левосторонний вывод: J => AbBb => BbaBb => CbaaBb => baaaBb => baaaCba => baaabaa;Правосторонний вывод: J => AbBb => AbCba => Abbaa => Bbabaa => Cbaabaa => baaabaa. Грамматика G1 вне зависимости от направления вывода формирует для заданной начальной цепочки AbBb единственную цепочку терминальных символов языка L(G 1): L(G 1) = {ba3ba2}Грамматика типа 1 это контекстно-зависимая грамматика или грамматика непосредственных составляющих (HC-грамматика). Второе название грамматики объясняется тем, что любую цепочку можно разложить на синтаксические составляющие (члены предложения естественного языка) и выполнить разбор каждой синтаксической переменной (части речи естественного языка) в составе синтаксической составляющей. В естественных языках для этого проводят грамматической разбор структуры предложения. В языках программирования - грамматический разбор структуры программы, что всегда необходимо при трансляции исходной программы на язык вычислительной машины. Продукции этой грамматики имеют вид: ω1Aω2 ::= ω1βω2,где A  VN;ω1, ω2, β  V*;ω1 – левый контекст;ω2 – правый контекст. Каждый шаг вывода состоит в замене одного вхождения нетерминального символа вхождением цепочки терминальных и/или нетерминальных символов. Эта замена обусловлена наличием левого и правого контекстов. Для HC-грамматики существенным является исполнение условия: |ω1Aω2| ≤ |ω1βω2|где |. . . | означает длину цепочки символов, заключенных между вертикальными линиями. Это требует исполнения в каждом правиле второго условия: β ≠ ε. Грамматики, в которых все правила обладают этими свойствами называют неукорачивающими. Множество языков HC-грамматики является собственным подмножеством языков грамматики типа 0. Для HC-грамматики возможны случаи: 1) ω1A ::= ω1β, когда ω2 = ε, 2) Aω2 ::= βω2, когда ω1 = ε. Для HC-грамматик также допустим лево- и правосторонний вывод, когда продукции грамматики применяются к самому левому или самому правому нетерминальному символу анализируемой цепочки. Пример. Пусть дана грамматика G5 = , где VT = {a; b; c}; VN = {B; c; J};Р = {р1: J ::= aJBC I aBC; p2: CB ::= DB;р3: DB ::= DC; p4: DC ::= BC; p5: aB::=ab; р6: bB ::= bb; p7 bC ::= bc; р8: cC ::= cc}. Какие цепочки терминальных символов формирует грамматика? В каждом правиле есть либо левый, либо правый контексты. Используем также левосторонний вывод терминальных цепочек:J => aBC => abC => abc; J => aJBC => ааВСВС => aabCBC => aabDBC => aabDCC => aabBCC => aabbCC => aabbcC => aabbcc = a2b2c2;J => aJBC => aaJBCBC => . . . => aaabbbccc = a2b2c2 и т. д. Грамматика G5 формирует цепочки терминальных символов, используя операцию итерации:L(G 5) = {aibici | i = 1; 2; 3;…}


Не сдавайте скачаную работу преподавателю!
С помощью нашего сервиса Вы можете собрать свою коллекцию шпаргалок по нужному предмету, и распечатать готовые ответы в удобном для вырезания виде. Для этого начните собирать ответы, добавляя в "Мои шпаргалки".

Доработать Узнать цену работы по вашей теме
Поделись с друзьями, за репост + 100 мильонов к студенческой карме :

Делаем шпаргалки правильно:
! Шпаргалки для экзаменов Какие бывают шпаргалки, как их лучше подготовить и что писать.
! Делаем правильную шпаргалку Что представляет собой удобная и практичная шпаргалка, как ее сделать.
! Как воспользоваться шпаргалкой В какой момент лучше достать шпаргалку, как ей воспользоваться и что необходимо учесть.

Читайте также:
Сдаем экзамены Что представляет собой экзамен, как он проходит.
Экзамен в виде тестирования Каким образом проходит тестирование, в чем заключается его суть.
Готовимся к экзаменам Как правильно настроиться, когда следует прекратить подготовку и чем заниматься в последние часы.
Боремся с волнением Как преодолеть волнение, как внушить себе уверенность.
Отвечаем на экзамене Как лучше отвечать и каким идти к преподавателю.
Не готов к экзамену Что делать если не успел как следует подготовиться.
Пересдача экзамена На какое время назначается пересдача, каким образом она проходит.
Микронаушники Что такое микронаушник или "Профессор .. ллопух ...".

Виды дипломных работ:
выпускная работа бакалавра Требование к выпускной работе бакалавра. Как правило сдается на 4 курсе института.
магистерская диссертация Требования к магистерским диссертациям. Как правило сдается на 5,6 курсе обучения.