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




НазваниеКонспект лекций доцента и. А. Волковой по курсу «системы программирования»
страница6/20
Дата публикации28.06.2013
Размер0.69 Mb.
ТипКонспект
lit-yaz.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Конспект лекций по курсу «Объектно-ориентированное программирование»
Б. Страуструп. Язык программирования C++, 3-е изд./Пер с англ. – Спб.; М.: «Невский диалект» – «Издательство бином», 1999 г. – 991...

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

Конспект лекций доцента и. А. Волковой по курсу «системы программирования» iconВ. Г. Баула Введение в архитектуру ЭВМ и системы программирования
Мгу им. М. В. Ломоносова. По данному курсу существует достаточно обширная литература, посвящённая программированию на Ассемблере,...

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

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

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

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

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

Конспект лекций доцента и. А. Волковой по курсу «системы программирования» iconКонспект лекций по дисциплине вгипу, 2009 Конспект лекций по дисциплине «Управление персоналом»
Крупица В. В., Яшкова Е. В., Егоров Е. Е. Управление персоналом: Конспект лекций по дисциплине – вгипу, 2009

Конспект лекций доцента и. А. Волковой по курсу «системы программирования» iconКонспект лекций. (Электронный учебник) Минск: бгэу, 2010. Тема 1...
Короленок Г. А. Менеджмент в торговле. Конспект лекций. (Электронный учебник) Минск: бгэу, 2010



Образовательный материал



При копировании материала укажите ссылку © 2013
контакты
lit-yaz.ru
главная страница