Решение задач к государственному экзамену по курсу «Технологии разработки ПО»

Вопросы к государственному экзамену по курсу «Технологии разработки ПО»

Направление подготовки магистров

09.04.01 Информатика и вычислительная техника

Знать:

1. Виды формальных грамматик. Понятие порождающей грамматики.

2. Классификация языков по Хомскому.

3. Бесконтекстные грамматики, деревья выводов.

4. Описание языка с помощью нормальных форм Бэкуса-Наура.

5. Семантика конструкций языка программирования.

6. Задание семантики операторов в виде тройки Хоара. Слабейшее предусловие.

7. Методы формальной спецификации и верификации программ.

8. Схемы программ. Способы представления схемы программы.

Уметь и владеть:

Задачи к государственному экзамену по курсу «Технологии разработки ПО»

Направление подготовки магистров

09.04.01 Информатика и вычислительная техника

1.Дана грамматика Г=<V,W,I,R>, где V={a,b,c}, W={A,B,C,I},

схема R: 1. I®ABI, 2. ABA®C, 3. AB®bc, 4. CB®a, 5. cI®c, 6. aI®a.

Построить несколько полных выводов в этой грамматике.

2. Дана грамматика Г=<V,W,I,R>, где V={a,b}, W={A,В,I},

схема R: 1. I®BA, 2. B®aBb, 3. B®ab, 4. A®Aa, 5. A®a.

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

3. Построить грамматику, порождающую язык L(Г)={aⁿ½n=1,2,…}.

4. Дана грамматика Г = <V,W,I,R>, где V={a,b,c,d}, W={A,B,C,D,I},

схема R:1. I®aA, 2. I®bB, 3. I®cC, 4. I®dD, 5. A®b,6. B®c, 7. C®d,

8. D®a. Построить язык, порождаемый этой грамматикой.

5. Построить грамматику, порождающую язык L={aⁿbⁿ| n=1,2,…}.

6. Построить дерево вывода формулы:

ù (а₂&a₃)É((a₄Úùa₁)&(ùa₂Éa₆)).

Язык, описывающий правильно построенные формулы логики высказываний с операциями конъюнкции &, дизъюнкции Ú, импликации É, отрицания ù над элементарными высказываниями a₁,…,а_n порождается КС-грамматикой со схемой R: I®(I), I®I&I, I®IÚI, I®IÉI, I®ùI, I®a_i (i=1,2,…n).

7. Язык L={a²ⁿ^-1| n = 1,2,…} порождается КС-грамматикой со схемой R: I®IaI, I®a. Показать, что эта грамматика является неоднозначной.

8. КС-грамматика для построения арифметических выражений с операциями сложения и умножения чисел a,b,c имеет схему R: I®I+I, I®I´I, I®a, I®b, I®c. Построить деревья выводов для цепочек (a´b)+c и a´(b+c).

9. Преобразовать в КС-грамматику совокупность металингвистических формул:

1. <целое> :: = <целое бзн>| + <целое бзн>| - <целое бзн>;

2. <целое бзн> :: = <цифра>| <целое бзн> <цифра>| <цифра> <целое бзн>;

3. <цифра> :: = 0| 1| 2| …| 9. Представить деревья выводов по этой грамматике цепочек +3748 и -1569.

10. Определить следующие понятия с использованием нотаций Бэкуса-Наура:

<буква>,<цифра >,<идентификатор>.

11. Определить понятие арифметических операций с использованием нотаций Бэкуса-Наура.

12. Определить понятие арифметического выражения с использованием нотаций Бэкуса-Наура.

13. Задана тройка Хоара: {x>5} y:=x*2 {y>1}. Определить слабейшее предусловие.

Ответы на вопросы к государственному экзамену по курсу «Технологии разработки ПО»

Вопрос.

Разработаны два основных вида формальных грамматик:

порождающая – строит любые правильные цепочки, давая при этом указания об их построении, и не строит ни одной неправильной цепочки;

распознающая – для любой предъявленной цепочки выясняет, является она правильной или нет.

Назовем словарем (или алфавитом) непустое конечное множество некоторых символов, а цепочкой (словом) в заданном словаре – произвольную конечную последовательность символов из словаря. Порождающей грамматикой Г называют упорядоченную четверку Г=<V,W,I,R>, где V={a,b,c,…} – терминальный (основной) словарь – конечная совокупность терминальных символов a,b,c,…;

W={A,B,C,D,I,…} – нетерминальный (вспомогательный) словарь – конечная совокупность нетерминальных символов A,B,C,D,I,…;

(использованы традиционные обозначения, сложившиеся в теории грамматик: символы терминального словаря – малыми латинскими буквами, нетерминальные – большими буквами);

всегда VÇW = Æ;

I – начальный символ (выделенный нетерминальный символ);

R – конечное множество правил грамматики (схема грамматики).

Цепочка (слово) в словаре VÈW это конечная последовательность символов из словарей V и W; такие цепочки будем обозначать греческими буквами a, b, g, x, …, w.

Терминальная цепочка – цепочка, состоящая только из терминальных символов словаря V.

Пустая цепочка L - цепочка, не содержащая ни одного символа.

Длиной | a | цепочки a называют количество входящих в цепочку символов. Так, если a = abADc, то | a | = 5. Ясно, что если | a | = 0, то a=L, и наоборот.

В общем случае каждое правило в схеме R имеет вид

a®b,

где a, b - соответственно левая и правая части правила, есть цепочки в словаре VÈW, а символ ® не входит в VÈW.

Правило (1) читается так: "цепочку a можно заменить на цепочку b".

В каждой схеме R должно быть хотя бы одно правило вида I®b, с которого начинается построение любой цепочки.

Языком L (Г), порождаемым грамматикой Г, называют множество всех терминальных цепочек, выводимых в этой грамматике из ее начального символа.

Вопрос.

Общепринятой является классификация, введенная Хомским, в основу которой положены ограничения на правила грамматики.

Приведем эту классификацию.

1. НС-грамматика (грамматика составляющих, контекстная грамматика): каждое правило в R имеет вид

x₁Аx₂ ® x₁wx₂, (1)

где x₁, x₂, w - произвольные цепочки в словаре VÈW, w¹L, A – символ из W.

Так как возможность реализации правила (1) зависит от символов, окружающих А, т.е. от контекста, в котором находится заменяемый символ А, то отсюда терминология: x₁, x₂ – левый и правый контексты, пара (x₁, x₂) – контекст правила, правила вида (1) – контекстные и сама грамматика контекстная.

2. КС-грамматика (бесконтекстная, контекстно-свободная грамматика): каждое правило в R имеет вид

А ® w, (2)

где w - цепочка в словаре VÈW, A – символ из W.

Так как (2) получается из (1) при x₁ = x₂ = L, т.е. при отсутствии контекста, то правила вида (2) – бесконтекстные и сама грамматика бесконтекстная.

3. А-грамматика (автоматная грамматика): каждое правило в R имеет вид

A®aB или A®a, (3)

где А, В – символы из W, а – символ из V.

4. Грамматику, не относящуюся ни к одному из трех указанных типов, будем называть грамматикой произвольного вида.

Языки, порождаемые НС-, КС- и А-грамматиками называют соответственно НС-, КС- и А-языками (контекстным, бесконтекстным, автоматным).

Вопрос.

КС-грамматика (бесконтекстная, контекстно-свободная грамматика): каждое правило в R имеет вид

А ® w,

где w - цепочка в словаре VÈW, A – символ из W.

В КС-грамматике (бесконтекстной) полные выводы наглядно и компактно представимы деревьями выводов. Дерево вывода строится сверху вниз, корень дерева соответствует начальному символу, висячие вершины соответствуют терминальным символам, остальные – нетерминальным символам.

Каждому правилу вида, например, A®aBCab соответствует фрагмент дерева

где три вершины a,a,b – висячие, поэтому дальше ребра идут только от вершин В и С в соответствии с правилами В®w, С®h, где w,h - цепочки в словаре VÈW.

Вывод закончен, т.е. дерево вывода построено, когда все висячие вершины построенного дерева соответствуют терминальным символам. Тогда читаемые слева направо терминальные символы образуют терминальную цепочку.

Высотой h построенного дерева вывода называют длину максимального из путей, ведущих из корня дерева в висячие вершины. Т.к. каждая вершина дерева, соответствующая нетерминальному символу, означает применение конкретного правила вывода, то сложность вывода, т.е. число примененных правил при построении вывода, равна числу нетерминальных символов в построенном дереве.

Вопрос.

Для определения синтаксиса языка существуют формы Бэкуса-Наура (БНФ). Описание языка с помощью нормальных форм Бэкуса представляет собой совокупность металингвистических формул вида

X :: = Y₁| Y₂| …|Y_n , (1)

где Х – текст, заключенный в угловые скобки < … > - металингвистическая переменная,

Y_i (i =1,n) – последовательность металингвистических переменных и основных символов языка (букв, цифр, скобок, неделимых слов else, if, …),

:: = – металингвистическая связка, читаемая как «есть» или «это»,

| – связка “или”.

Металингвистическая переменная – это имя конструкции языка, а металингвистическая формула – это описание различных синтаксических вариантов строения конструкции Х в левой части (1) через другие конструкции и основные символы языка, указанные в правой части (1). Перечисление вариантов справа в (1) производится с помощью связки | (или).

Любая синтаксически корректная программа, написанная на некотором языке программирования, может быть определена в нотации БНФ как нетерминальный символ некоторого языка.

Контекстные грамматики, в которых вид левой части каждой продукции может быть ограничен лишь единственным нетерминальным символом, имеют название контекстно свободных грамматик.

Пример. Строка из одних цифр, имеющая любую длину, начиная с 1, определяется как целое без знака (сокращенно: целое бзн). Целое, которое может иметь знак (а может и не иметь) определяется следующей совокупностью металингвистических формул:

3. <целое> :: = <целое бзн>| + <целое бзн>| - <целое бзн>;

4. <целое бзн> :: = <цифра>| <целое бзн> <цифра>| <цифра> <целое бзн>;

5. <цифра> :: = 0| 1| 2| …| 9.

Вопрос.

Кроме синтаксиса важно дать точное описание семантики (смысла) всех конструкций языка программирования. Это необходимо для решения следующих задач:

1. доказательство правильности программ, то есть что эта программа при реализации выдает тот же результат, который нужен по смыслу решаемой задачи

Доказательство правильности программы сводится к выполнению двух задач:

a. Создание точной формальной спецификации программы

Спецификация – это формальное описание результата, который должен быть получен при реализации программы на допустимой области изменения исходных данных.

b. Верификация программы – это формальное доказательство правильности программы в соответствии с заданной спецификацией.

В практике программирования вместо верификации чаще всего применяют тестирование, но никакое тестирование не может доказать правильность программы. Оно может только выявить имеющиеся ошибки.

2. создание компиляторов с данного языка программирования

В настоящее время имеется несколько подходов к формализации семантики программ

1. Операционная семантика

Здесь смысл программы и отдельных ее конструкций задается некоторым четко описанным множеством операторов, которые могут быть реализованы на некоторой реальной или виртуальной машине

Пример: машина Тьюринга

2. Аксиоматическая семантика

Семантику каждой синтаксической конструкции языка задают в виде аксиом, которым должны удовлетворять исходные данные, и правил вывода, с помощью которых может быть получен результат (как теорема, которая вытекает их аксиом с помощью правил вывода), то есть эта семантика является расширением математической теории исчисления предикатов, которая в математике используется для доказательства теорем.

В частности данный подход используется в языке программирования Prolog.

Вопрос.

Аксиоматическая семантика операторов или некоторого фрагмента программы задается в виде тройки Хоара: {Q} S {R}, где Q,R – предикаты, S – фрагмент программы или отдельный оператор.

Смысл тройки: «Если выполнение S началось в состоянии, удовлетворяющем Q, то имеется гарантия, что оно завершится через конечное время, в состоянии, удовлетворяющем R». При этом Q называют предусловием (входным утверждением) программы/оператора S, а R – постусловием (выходным утверждением) S.

Пример: {x>0} y:=x+1 {y>1}

Важно отметить: для заданных S и R существует бесконечное количество возможных предусловий. Например, для этого примера правильным будет предусловие x>10.

Среди всего множества предусловий существует слабейшее предусловие, которое задает наиболее широкое множество исходных данных. В данном примере слабейшее предусловие: x>0.

Слабейшее предусловие обозначается символом: wp(S,R)

Вопрос.

Для доказательства правильности программ необходимо задать формальную спецификацию, в которой формально задается результирующее постусловие R.

Имеется большое количество различных языков спецификации:

§ Исполнимые спецификации (RSL,SDL)

§ Алгебраические спецификации (ASN, подмножество языка ADA) и др.

Верификация программы сводится к доказательству правильности (корректности) программ и включает два этапа:

1. Доказательство завершаемости программы, то есть того факта, что при любых исходных данных (из допустимого множества) эта программа завершится за конечное время.

2. Доказательство того факта, что завершившаяся программа выдает результат, удовлетворяющий спецификации

Имеется два основных метода верификации программ:

1. Метод индуктивных утверждений (Флойд, Наур)

2. Метод Хоара-Дейкстры (основан на тройках Хоара и преобразователях предикатов)

Вопрос.

Схема программы – это абстрактная модель программы, которая описывает только структуру программы и не задает никаких типов данных, никаких конкретных функций и предикатов, и никаких конкретных значений переменных и констант.

На схеме программы указываются только связи между операторами и задаются абстрактные символы функций и предикатов. Одна и та же схема программы может соответствовать многим конкретным программам.

1. Графический

2. Аналитический

3. Алгебраический

На схемах программ можно решать следующие задачи:

1. Распараллеливание вычислительного процесса

Представление схемы программы (рисунок 1, рисунок 2) содержат всю информацию о структуре логических и информационных связей (ИЛГ)

2. Оптимизация программ по критерию минимума объема памяти или по критерию минимума затрат времени, но в последнем случае необходимо задавать затраты времени на выполнение операторов

3. Трансляция программ

Теория схем программ дает базу для грамотного решения современных задач, связанных с разработкой параллельных программ для многопроцессорных вычислительных систем.

Решение задач к государственному экзамену по курсу «Технологии разработки ПО»

Направление подготовки магистров

09.04.01 Информатика и вычислительная техника

Решение задачи 1.

Строим полные выводы:

I ABI bcI bc;

I ABI ABABI bcbcI bcbc = (bc)²;

I ABI ABABI ABABABI bcbcbcI bcbcbc = (bc)³;

Выводы строятся по схеме: правило 1 – n раз, правило 3 – n раз, правило 5 – 1 раз; такую схему будем обозначать как

1ⁿ, 3ⁿ, 5¹.

Применение этой схемы приводит к цепочкам вида (bc)ⁿ, n = 1,2,…

Полные выводы в данной грамматике можно строить и по другой схеме:

I ABI ABABI CBI aI a;

I ABI ABABI ABABABI ABABABABI CBCBI aaI aa = a²;

I ABI ABABI ABABABI ABABABABI ABABABABABI

ABABABABABABI CBCBCBI aaaI aaa = a³;

эти выводы построены по схеме:

1²ⁿ, 2ⁿ, 4ⁿ, 6¹,

приводящей к цепочкам aⁿ, n = 1,2,…

Решение задачи 2.

Строим полные выводы:

I BA abA aba;

I BA abA abAa abaa = aba²;

I BA abA abAa abAaa abaaa = aba³;

(схема вывода 1¹, 3¹, 4ⁿ, 5¹ приводит к цепочкам abaⁿ ⁺¹ , n = 0,1,2,…

I BA aBba aabbA aabba = a²b²a;

I BA aBbA aaBbbA aaabbbA aaabbba = a³b³a;

I BA aBbA aaBbbA aaaBbbbA aaaabbbbA aaaabbbba = a⁴b⁴a;

(схема вывода 1¹, 2ⁿ, 3¹, 5¹ приводит к цепочкам aⁿ ⁺¹ bⁿ ⁺¹ a , n = 1,2,…

I BA aBbA aabbA aabbAa aabbaa = a²b²a²;

I BA aBbA aabbA aabbAa aabbAaa aabbaaa = a²b²a³;

I BA aBbA aaBbbA aaabbbA aaabbbAa aaabbbaa = a³b³a²;

(схема вывода 1¹, 2^k, 3¹, 4^m, 5¹ приводит к цепочкам a^k⁺¹b^k⁺¹a^m⁺¹, k,m = 1,2,…).

Из приведенных полных выводов и их схем видно, что данная грамматика порождает язык

L(Г) = {aⁿbⁿa^m| n,m = 1,2,…}.

Решение задачи 3.

3. Терминальный словарь: V={a}; нетерминальный словарь: W={I}. Т.к. грамматика должна порождать цепочки а, аа, ааа, аааа, …, то схема грамматики:

R₁: 1. I®a, 2. I®aI или R₂: 1. I®a, 2. I®Ia

(получением нескольких выводов в этом легко убедиться).

Так как обе грамматики Г₁=<V,W,I,R₁> и Г₂=<V,W,I,R₂> порождают один и тот же язык L={aⁿ| n=1,2,…}, то эти грамматики эквивалентные.

Если терминальный символ а трактовать как символ 1, то язык L содержит все цепочки вида 1, 11, 111, 1111, …, т.е. описывает множество всех натуральных чисел, заданных в унарной записи.

Решение задачи 4.

4. В этой грамматике всего 4 выводимых цепочки:

I aA ab, I bB bc, I cC cd, I dD da,

следовательно, язык порождаемый этой грамматикой, это L(Г) = {ab, bc, cd, da}.

Если терминальные символы a,b,c,d трактовать как ориентированные отрезки

то цепочкам ab, bc, cd и da соответствуют геометрические фигуры (прямые углы).

т.е. в этом случае грамматика Г порождает язык, описывающий указанные 4 прямых угла.

Решение задачи 5.

Необходимо построить цепочки вида ab, aabb, aaabbb, …

Возьмем V={a,b}, W={I}. Цепочку ab (при n=1) получаем, вводя правило I®ab; остальные цепочки с учетом симметрии их относительно а и b можно получить, ведя правило I®aIb. Таким образом, предлагается схема R: 1. I®ab, 2. I®aIb.

Схема полного вывода 2ⁿ^{– 1}, 1¹ (n = 1,2,…) дает все цепочки aⁿbⁿ.

Решение задачи 6.

Введение скобок делает эту грамматику однозначной, т.е. каждая формула логики высказываний имеет единственное дерево вывода. На рис. 1 представлено дерево вывода формулы.

(

)

a₆

a₃

a₂

(

)

(

)

a₄

(

)

a₁

Высота построенного дерева h = 7, сложность вывода равна 18.

Решение задачи 7.

Если построить, например, дерево вывода цепочки а⁷, то легко обнаружить, что таких деревьев несколько.

Рис.2. Деревья вывода цепочки а⁷.

Заметим, что можно построить и другие деревья вывода цепочки a⁷.

Рассмотренный пример свидетельствует о том, что одна и та же цепочка может иметь не одно дерево вывода.

КС-грамматика называется неоднозначной, если хотя бы одна цепочка в порождаемом ею языке имеет более одного дерева вывода. В противном случае, когда каждая цепочка имеет единственное дерево вывода, грамматика называется однозначной.

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

Рис. 5

Рис. 6

(

)

(

)

(a´b)+c

a´(b+c)

Решение задачи 8.

Решение задачи 9.

Перепишем формулы без связки | :

1. <целое> :: = <целое бзн>, <целое> :: = + <целое бзн>,

<целое> :: = - <целое бзн>;

2. <целое бзн> :: = <цифра>, <целое бзн> :: = <целое бзн> <цифра>,

<целое бзн> :: = <цифра> <целое бзн>;

3. <цифра> :: = 0, <цифра> :: = 1, <цифра> :: = 2, … , <цифра> :: = 9.

Основные символы +, -, 0, 1, 2, …, 9 метаязыка запишем как терминальный словарь КС-грамматики

V = {+, -, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.

Металингвистическим переменным <целое>, <целое бзн>, <цифра> поставим в соответствие нетерминальные термины I, A, B соответственно, т.е. W={I,A,B}.

Тогда формулы 1.-3. метаязыка запишутся следующей системой правил R КС-грамматики с указанными словарями V и W:

1. I ® A, I ® +A, I ® -A,

2. A ® B, A ® AB, A ® BA,

3. B ® 0, B ® 1, - - - - - B ® 9.

Рис.

На рис. представлены деревья выводов по этой грамматике цепочек +3748 и -1569.

Отметим, что эта грамматика неоднозначна, т.к. нетрудно для этих же цепочек построить другие деревья вывода.

Решение задачи 10.

<буква>::=a½b½c½d½e½f½g½h½i½j½k½l½m½n½o½p½q½r½s½t½u½v½w½x ½y½z½a½b½c½d½e½f½g½h½i½j½k½l½m½n½o½p½Q½r½s½t½

u½v½w½x½y½Z.

<цифра>::= 0½1½2½3½4½5½6½7½8½9.

Понятие идентификатора.

<идентификатор>::= <буква>½<идентификатор><буква>½

_<идентификатор>½<идентификатор>_½<идентификатор><цифра>.

Решение задачи 11.

<унарная операция>::= ++½--½-

<бинарная операция>::= *½/½+½-

<арифметическая операция>::=<унарная операция>½<бинарная операция>.

Решение задачи 12.

Проведем разбор понятия арифметическое выражение. Арифметическое выражение – это операнды, объединенные знаками арифметических операций. Синтаксис любого алгоритмического языка описывается с использованием нотаций Бэкуса – Наура (БНФ).

<арифметическое выражение>::=<операнд><унарная операция>½

<унарная операция><операнд>½<операнд><бинарная операция><операнд>

<операнд>::=<константа>½<переменная>½<обращение к функции>½ (<арифметическое выражение>)

<константа>::= <идентификатор>½<константа>

<переменная>::= <идентификатор>

<обращение к функции>::= <идентификатор>(<список аргументов>)

(<список аргументов>)::= [<константа>[, <переменная>…]]

Решение задачи 13.

Среди всего множества предусловий существует слабейшее предусловие, которое задает наиболее широкое множество исходных данных. В данном задании слабейшее предусловие: x>0.

Слабейшее предусловие обозначается символом: wp(S,R)

Дата добавления: 2019-09-13; просмотров: 154; Мы поможем в написании вашей работы!

Поделиться с друзьями:

Мы поможем в написании ваших работ!