Определить понятие арифметических операций с использованием нотаций Бэкуса-Наура.
Понятие области допустимых решений. Примеры ОДР.
Область допустимых решений - это множество всех возможных точек (значений переменных) задачи оптимизации, которые удовлетворяют ограничениям задачи. Эти ограничения могут включать неравенства, равенства и требование целочисленности решения. м
При ограничениях в виде неравенств точка может быть либо внутренней точкой (допустимой точкой), либо граничной точкой (допустимой точкой), либо внешней точкой (недопустимой точкой).
Если ограничения задачи оптимизации совместно противоречивы, не существует точки, которая бы удовлетворяла всем ограничениям, а тогда область допустимых решений пуста. В этом случае задача не имеет решений и говорят, что она недопустима
Выпуклая область допустимых решений — это множество решений, в котором отрезок, соединяющий два допустимых решения, содержит только допустимые точки и не проходит через какую-либо недопустимую точку.
Множество допустимых решений может быть ограниченным или неограниченным.
Например, множество допустимых решений, определяемое ограничениями {x ≥ 0, y ≥ 0}, является неограниченным, поскольку в некоторых направлениях можно идти бесконечно, оставаясь в области допустимых решений.
Множество допустимых решений, образованное ограничениями {x ≥ 0, y ≥ 0, x + 2y ≤ 4}, является ограниченным, поскольку движение в любом направлении ограничено.
|
|
|
| 3 x1 | + | 5 x2 | ≤ | 32 | ||
x1 ≥ 0
x2 ≥ 0
Шаг 1
Рассмотрим неравенство 1 системы ограничений.
3 x1 + 5 x2 ≤ 32
Построим прямую: 3 x1 + 5 x2 = 32
Пусть x1 =0 => 5 x2 = 32 => x2 = 32/5
Пусть x2 =0 => 3 x1 = 32 => x1 = 32/3
Рис.1
Найдены коородинаты двух точек (0, 32/5) и (32/3 ,0). Соединяем их и получаем необходимую прямую.
Для определения требуемых точек, вернемся к исходному неравенству.
3 x1 + 5 x2 ≤ 32
Перенесем все в правую часть неравенства, оставив в левой части только x2
5 x2 ≤ - 3 x1 + 32
x2 ≤ - 3/5 x1 + 32/5
Знак неравенства ≤ , следовательно, нас интересуют точки расположенные ниже построенной прямой.
Объединим данное условие с рисунком. В итоге получим область допустимых решений, изображенную на рисунке 1.
Виды формальных грамматик. Понятие порождающей грамматики.
Формальная грамматика или просто грамматика в теории формальных языков — способ описания формального языка, то есть выделения некоторого подмножества из множества всех слов некоторого конечного алфавита. Различают порождающие и распознающие (или аналитические) грамматики — первые задают правила, с помощью которых можно построить любое слово языка, а вторые позволяют по данному слову определить, входит ли оно в язык или нет.
|
|
|
· Терминал (терминальный символ) — объект, непосредственно присутствующий в словах языка, соответствующего грамматике, и имеющий конкретное, неизменяемое значение (обобщение понятия «буквы»). В формальных языках, используемых на компьютере, в качестве терминалов обычно берут все или часть стандартных символов ASCII — латинские буквы, цифры и спец. символы.
· Нетерминал (нетерминальный символ) — объект, обозначающий какую-либо сущность языка (формула, арифметическое выражение, команда) и не имеющий конкретного символьного значения.
Типы грамматик
По иерархии Хомского, грамматики делятся на 4 типа, каждый последующий является более ограниченным подмножеством предыдущего (но и легче поддающимся анализу):
· тип 0. неограниченные грамматики — возможны любые правила
· тип 1. контекстно-зависимые грамматики — левая часть может содержать один нетерминал, окруженный «контекстом» (последовательности символов, в том же виде присутствующие в правой части); сам нетерминал заменяется непустой последовательностью символов в правой части.
· тип 2. контекстно-свободные грамматики — левая часть состоит из одного нетерминала.
|
|
|
· тип 3. регулярные грамматики — более простые, эквивалентны конечным автоматам.
Кроме того, выделяют:
· Неукорачивающиеся грамматики. Каждое правило такой грамматики имеет вид 
Длина правой части правила не меньше длины левой
· Линейные грамматики. Каждое правило такой грамматики имеет вид 
, то есть в правой части правила может содержаться не более одного вхождения нетерминала
Порождающие грамматики
Словами языка, заданного грамматикой, являются все последовательности терминалов, выводимые (порождаемые) из начального нетерминала по правилам вывода.
Чтобы задать грамматику, требуется задать алфавиты терминалов и нетерминалов, набор правил вывода, а также выделить в множестве нетерминалов начальный.
Порождающей грамматикой Г называют упорядоченную четверку Г=<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 (Г), порождаемым грамматикой Г, называют множество всех терминальных цепочек, выводимых в этой грамматике из ее начального символа.
Определить понятие арифметических операций с использованием нотаций Бэкуса-Наура.
Нотация Дж. Бэкуса и П.Наур используют зарезервированные метасимволы «::=» и «|», которые читаются как «является» и «или», определяемые понятия, которые выделяются посредством угловых скобок «á» и «ñ», и символы алфавита языка (которые называются терминальными символами). Каждое правило (определение) в этой нотации имеет вид определяемое понятие ::= серия альтернатив разделённых «|»
форма Бэкуса-Наура (БНФ) состоит из правил подстановки, определяющих как нетерминальный символ (т.е. символ, требующий дальнейшего уточнения) может быть замещен другим нетерминальным или терминальным символом (т.е. символом, не требующим уточнения).
Определение простейшего арифметического выражения с помощью БНФ выглядит следующим образом:
<унарная операция>::= ++½--½-
<бинарная операция>::= *½/½+½-
<арифметическая операция>::=<унарная операция>½<бинарная операция>.
Примеры простейших арифметических выражений, соответствующих данному определению: X+Y X * (Y + Z) и т.д.
Дата добавления: 2019-07-17; просмотров: 217; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!