Конспект лекций доцента и. А. Волковой по курсу «системы программирования»




НазваниеКонспект лекций доцента и. А. Волковой по курсу «системы программирования»
страница6/20
Дата публикации24.05.2014
Размер0.69 Mb.
ТипКонспект
literature-edu.ru > Лекции > Конспект
1   2   3   4   5   6   7   8   9   ...   20

Классификация по Хомскому



Грамматики типа 0 (ноль) – грамматики, на правила которых не вводится никаких ограничений.
Грамматики типа 1:

  • неукорачивающие – если α -> β, и |α| <= |β|, (может сделать цепочку только длиннее)

  • КЗ (контекстно-зависимые грамматики) – грамматики с условием:

α = ξ1Αξ2 ->ξ1γξ2, ξ1ξ2 є (VT U VN)*, γ є (VT U VN)+, A є VN.

Для любой неукорачивающей грамматики есть эквивалентная ей КЗ грамматика.

Если грамматика типа 1, необходимо уточнение.
Грамматики типа 2:

  • КС (контекстно-свободная)

N -> β - в левой части ровно 1 нетерминальный символ, β – любая цепочка, исключая пустую

N є VN, β є (VT U VN)+

  • УКС (укорачивающая КС)

Β є (VT U VN)*

Теоретически (по определению) УКС грамматика относится к типу 0, но рассматривается в типе 2, т.к. обладает одинаковыми свойствами с КС грамматикой и реализуется одними и теми же алгоритмами.

Класс языков, порождающих УКС, совпадает с классом языков, порождающих КС, в смысле “почти-эквивалентности”.
Грамматики типа 3:

регулярные – праволинейные и леволинейные. Каждое правило имеет вид

A -> t , t є VT - терминальный символ

A -> tB, A є VN - нетерминальный символ

Если в грамматике содержатся правила A -> t, A -> tB, Α -> Βt, то она не является регулярной.
Рассмотрим соотношения между типами грамматик.

P с КС с КЗ с тип 0 (здесь «с» – значок включения множеств).

Любая КС грамматика является УКС. УКС – грамматика типа 0, но она не является КЗ или КС.
Следует обратить внимание на ошибки в учебнике:

Пример. G1 = ({0,1},{A,S},P,S)

P: S -> 0A1

0A -> 00A1 -грамматика типа 0, т.к. есть ε.

A -> ε

Пример. G3 = ({0,1},{S},P,S)

P: S -> 0S1 | ε -грамматика УКС.

Язык называется языком типа К по Хомскому, если его можно описать грамматикой типа К, где К – максимально возможный номер.

Соотношения между языками такие же, как у грамматик.
Существует хотя бы один язык, который является КС языком, но не является P языком, т.к. Р с КС. Например, L(G) = {anbn | n>=1}.

Так же язык L(G) = {anbncn | n>=1} является КЗ, но не КС.
На стр.7 пособия ошибка – в примере, где указано, что это – язык типа 0, тот язык типа 1. Пример языка типа 0 авторы пособия пока не придумали, исключая тривиальные случаи.
Как из КЗ сделать язык типа 0?

L(G) = {anbncn | n>=1} исправить на L(G) = {anbncn | n>=0}


Пример грамматики.

P: S -> aSBC | abC

CB -> BC

bB -> bb => L(G) = {anbncn | n>=1}

bC -> bc

cC -> cc
вводим символ N, который не принадлежит алфавиту, заменяем 1 правило на 3, тогда они будут КЗ.

CB -> CN

CN -> BN

BN -> BC


Лекция 4. 02/03/2004.



Пример доказательства того, что данная грамматика порождает данный язык.

S -> (1) aSBC | (2) abC

CB -> (3) BC

bB -> (4) bb

bC -> (5) bc

cC -> (6) cc (в скобках указаны номера преобразований)

- грамматика из 6 правил.

L(G) = {anbncn | n>=1} – язык.
Нужно доказать:

  1. Любая цепочка выводится из начальной цели этой грамматики.

  2. Никакая другая грамматика не порождает этот язык.

1). Доказываем по индукции.

n=1

S -> (2) abC -> (5) abc

n>=1

S -> (1)aSBC -> (1) … {(n-1) раз применяем правило (1)} -> a n-1S(BC)n-1 ->

-> (2) anbC(BC) n-1 -> (3) … ->anbB n-1Cn -> (4) anbbBn-2Cn -> (4)… -> anbnCn ->

-> (5) … -> anbncn

2). Доказываем, что не получается других цепочек.
Выводы из правил:

1. Новые b | B, a, C появляются только после применения правил (1) и (2) в равных количествах.

=> В любой сентенциальной форме одинаковое количество a,b,c.

2. В заменяется только на b, С – на с.

3. Появившиеся терминальные символы не переставляются в цепочке, не меняют позиции.

4. Первый терминальный символ ‘b’ появляется только после применения правила (2).

5. ‘B’ заменяется на ‘b’ только, если слева стоит ‘b’ (следствие из правила 4).

=> Второе ‘b’ появляется только рядом с первым, все ‘b’ сгруппированы.

=> (из 3-5) Любое ‘b’ всегда стоит слева от с|С, ‘b’ – между ‘a’ и ‘c’.
Если язык описывается грамматикой определённого типа, это гарантирует, что разбор грамматики можно определить существующими алгоритмами.

1   2   3   4   5   6   7   8   9   ...   20

Похожие:

Конспект лекций доцента и. А. Волковой по курсу «системы программирования» iconРеспублики Беларусь Учреждение образования «белорусский государственный...
Конспект лекций по курсу «Основы алгоритмизации и программирования» для студентов всех специальностей и всех форм обучения. Мн.:...

Конспект лекций доцента и. А. Волковой по курсу «системы программирования» iconКонспект лекций «Логистика. Конспект лекций»
Конспект лекций соответствует требованиям Государственного образовательного стандарта высшего профессионального образования

Конспект лекций доцента и. А. Волковой по курсу «системы программирования» iconКонспект лекций по курсу "Информатика и использование компьютерных...
Конспект лекций предназначен для студентов филологического факультета и факультета гуманитарных и социальных наук рудн. Конспект...

Конспект лекций доцента и. А. Волковой по курсу «системы программирования» iconРабочая программа по курсу «основы Программирования на языке ассемблер»
Программа предназначена для обучения основам программирования на языке низкого уровня Ассемблере учащихся средних школ, учреждений...

Конспект лекций доцента и. А. Волковой по курсу «системы программирования» iconОсновы информатики и вычислительной техники системы программирования
Рассматриваются основные понятия языков программирования. Излагаются процедурный и объектный подходы в программировании. Более подробно...

Конспект лекций доцента и. А. Волковой по курсу «системы программирования» iconКонспект лекций для студентов специальности 1-25 01 04 «Финансы и...
...

Конспект лекций доцента и. А. Волковой по курсу «системы программирования» iconКонспект лекций для студентов специальности 1-54 01 01-04 «Метрология,...
Конспект лекций предназначен для студентов специальности 1-54 01 01-04 «Метрология, стандартизация и сертификация (лёгкая промышленность)»...

Конспект лекций доцента и. А. Волковой по курсу «системы программирования» iconАвтор: Медведева Г. В
Курс лекций содержит основные разделы языка программирования t-pascal, предусмотренные образовательным стандартом

Конспект лекций доцента и. А. Волковой по курсу «системы программирования» iconКонспект лекций для студентов пятого курса специальности 220400 Программное...
Данный конспект лекций составлен для студентов четвёртого курса специальности “Программное обеспечение вычислительной техники и автоматизированных...

Конспект лекций доцента и. А. Волковой по курсу «системы программирования» iconУчебник Толубеевой Т. И., доцента кафедры пти «Основы проектирования крупноузорчатых тканей»
Особенность Декады – 25- летие выхода в свет стандартов исо серии 9000 на системы менеджмента качества

Литература


При копировании материала укажите ссылку © 2015
контакты
literature-edu.ru
Поиск на сайте

Главная страница  Литература  Доклады  Рефераты  Курсовая работа  Лекции