Создан заказ №2397273
7 ноября 2017
Решить задачу 1 Сигнализирующие функции Изучая порождающие грамматики возникает ряд существенных вопросов
Как заказчик описал требования к работе:
Формальные языки и грамматики.
1. Сигнализирующие функции.
2. Дана грамматика. Постройте вывод заданной цепочки
Фрагмент выполненной работы:
Решить задачу.
1. Сигнализирующие функции.
Изучая порождающие грамматики, возникает ряд существенных вопросов, одним из которых является вопрос об оценке сложности их работы, т.е. сложности выводов. Для решения этого вопроса используются так называемые сигнализирующие функции.
Основными типами сигнализирующих функций являются:
Временная сложность;
Емкость;
Левая глубина;
Правая глубина;
Разброс;
Активная емкость.
Первая характеризует сложность вывода числом его шагов, вторая – объемом затрачиваемой «памяти» (носителями «памяти» в выводе естественно считать его промежуточные цепочки). (работа была выполнена специалистами Автор 24) Остальные типы функций являются сигнализирующими лишь для некоторых важных классов грамматик, например, НС-грамматик.
Отметим несколько свойств сигнализирующих функций:
Для произвольной грамматики Г следующие утверждения равносильны:
язык L(Г) рекурсивен;
любая сигнализирующая грамматика Г вычислима;
любая сигнализирующая грамматики Г мажорируется подходящей вычислимой функцией;
хотя бы одна сигнализирующая грамматики Г вычислима;
хотя бы одна сигнализирующая грамматики Г мажорируется вычислимой функцией. При этом по алгоритму, требуемому каким-либо одним из перечисленных утверждений, можно построить алгоритмы, требуемые остальными.
Для произвольной грамматики Г можно построить эквивалентную ей грамматику Г ', удовлетворяющую следующим условиям:
Г ' не имеет правил с пустой левой частью;
для любого полного вывода в Г, оканчивающегося цепочкой х, можно построить равносильный ему полный вывод в Г '
В теории сложности вычислений (машины Тьюринга) имеются разные степени инвариантности результатов. Наиболее общие для них (такие, как теоремы «сжимания» и «ускорения» Рабина и Блюма) формулируются для произвольного типа сигнализирующих, удовлетворяющих аксиомам Блюма.
Теоремы могут формулироваться как в терминах емкости памяти машин Тьюринга, так и переформулироваться для любых типов сигнализирующих (поскольку любые типы сигнализирующих общерекурсивно выражаются друг через друга). При этом, разумеется, «точность до порядка» перейдет в точность до некоторой другой общерекурсивной функции. Это огрубление неизбежно, если нужно получать результаты, годные во всех случаях, когда выполняются аксиомы Блюма.
Более тонкие проблемы обязательно будут иметь меньшую общность. Такова, например, проблема о соотношении необходимого объема памяти и времени работы алгоритмов. Эта проблема действительно имеет смысл для любых естественных типов машин, но не для произвольных сигнализирующих. Это тоже высокая степень инвариантности (гораздо большая, чем, например, в задачах о «вычислимости в реальное время»).
Для выделения задач такой степени инвариантности нужно формально описать используемые в них классы типов сигнализирующих (например, «емкость памяти любых естественных типов машин»). При этом, чем более узок этот класс, тем больше точность описания. Например, некоторые результаты дают возможность аналитически описать класс «емкости памяти произвольных естественных типов машин» с точностью до мультипликативной константы. А. А. Мучник поставил вопрос о возможности такого описания для «времени работы произвольных естественных типов машин». Иными словами, нужно аналитически ввести класс сигнализирующих, каждая из которых с некоторой точностью совпадала бы с временем работы какой-нибудь «естественной» машины; при этом должно быть интуитивно убедительно, что исчерпываются все типы машин, которые можно признать «естественными». Важным при этом будет вопрос о точности этого описания.
Несложно заметить, что все обычные типы сигнализирующих функций переводятся друг в друга функциями, элементарными по Кальмару. Это значит, что если согласиться на грубую точность, при которой функции f(х) и 2f(x) считаются эквивалентными, то задача, поставленная Мучником, станет тривиальной (при такой точности не будет, в частности, различия между временем работы и емкостью памяти). Можно привести определение «времени работы» с точностью до мультипликативной константы и затем до асимптотики в показателе степени. Эта точность, с одной стороны, достаточна для формулировки таких вопросов, как проблема перебора, проблема о соотношении емкости памяти и времени работы, а с другой стороны, оставляет свободу, достаточную, чтобы абстрагироваться от свойств отдельных алгоритмических систем и дать общее определение.
Из сказанного выше ясно, что понятие временной сложности вычисления функции можно определить с точностью до возведения в ограниченную степень, не связывая себя какими-нибудь специальными типами машин. Однако для постановки многих важных вопросов эта точность недостаточна.
2. Дана грамматика. Постройте вывод заданной цепочки
Решение:
S T – S T – T + S T – T + T F – T + T F – F*T + T F – F*F + T
F – F*F + F a – F*F + F a – b*F + F a – b*a + F a – b*a + b
Пояснения
Начинаем с S. Затем заменяем S на T – S (далее то, что заменяем, выделено полужирным). Затем в T – S заменяем S на T + S, получаем T – T + S. Далее заменяем S на T, получая T – T + T и т.д. до a – b*a + b.Посмотреть предложения по расчету стоимости
Заказчик
заплатил
заплатил
20 ₽
Заказчик не использовал рассрочку
Гарантия сервиса
Автор24
Автор24
20 дней
Заказчик принял работу без использования гарантии
8 ноября 2017
Заказ завершен, заказчик получил финальный файл с работой
5
Решить задачу
1 Сигнализирующие функции
Изучая порождающие грамматики возникает ряд существенных вопросов.jpg
2017-11-11 17:28
Последний отзыв студента о бирже Автор24
Общая оценка
5
Положительно
Автор работу выполнил очень быстро и на отлично.В выполнении работы им были учтены все мои уточнения и пожелания.Очень помог.Рекомендую!
Хочешь такую же работу?
300 ₽
