« Предыдущий вопрос
Реляционная логика. Основные понятия.

Известно, что соответствие, заданное на элементах одного множества X, называют отношением (relation)

Загрузка
Скачать Получить на телефон
например +79131234567

txt fb2 ePub html

на телефон придет ссылка на файл выбранного формата

Что это

Шпаргалки на телефон — незаменимая вещь при сдаче экзаменов, подготовке к контрольным работам и т.д. Благодаря нашему сервису вы получаете возможность скачать на телефон шпаргалки по математической логике. Все шпаргалки представлены в популярных форматах fb2, txt, ePub , html, а также существует версия java шпаргалки в виде удобного приложения для мобильного телефона, которые можно скачать за символическую плату. Достаточно скачать шпаргалки по математической логике — и никакой экзамен вам не страшен!

Сообщество

Не нашли что искали?

Если вам нужен индивидуальный подбор или работа на заказа — воспользуйтесь этой формой.

Следующий вопрос »
Формальные грамматики типа 2 и 3. Вывод цепочек терминальных символов.

Грамматика типа 2 - это контекстно-свободная грамматика (КС-грамматика). Правила этой грамматики не

Формальные грамматики типа 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(G1):
L(G1) = {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(G5) = {aibici | i = 1; 2; 3;…}