Определение грамматики. Понятие грамматики. Виды грамматики.

Определение грамматики. Понятие грамматики. Виды грамматики.

Грамматика – описание способа построения предложений некоторого языка (матем. сист., определяющая язык); любой конечный механизм задания языка.

Правило (продукция) – это упорядоченная пара цепочек символов ( ), для кот. справедливо ( ).

Сущ-ет 2 вида грамматик: порождающие – конечный набор правил, позволяющий строить все правильные предложения языка L, и применение которых не дает ни одного неправильного предложения; распознающие – задает критерий принадлежности произвольной цепочки данному языку, это фактически некоторый алгоритм, принимающий в качестве входа символ за символом произвольную цепочку над словарем V и дающий на выходе один из двух возможных ответов: либо ∊L, либо нет (автоматы).

Грамматика задается G=(VT, VN, P, S) – порождающая, VT – алфавит терминальных символов (символ, входящий в алфавит выходного языка), VN – нетерминальных (любые символы, кот исп-ся грамматикой для реализации правил этих грамматик. Нетермин. символы выр-ся через другие нетерм символы, терм символы и через самих себя). VT VN= (пересечение множеств невозможно). Р – набор правил вида (Здесь a и b – это цепочки из символов объединенного словаря, – разделитель правила на правую и левую части). Грамматика может содержать любое количество правил. S–целевой (начальный) символ грамматики, выделенный элемент нетерминального словаря. V= VT VN – полный алфавит G.

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

Задача 1. Если задана некоторая грамматика G, то возникает вопрос: какой язык порождает G?

G= {V, N, S, R}, V= {a, b, c}, N= {A, B, S},

R: bA®abc; aS®bAc; S®caS;bAB®ab. Вывод начинается с символа S – начального символа грамматики:

S, caS, (ca)²S, (ca)³S, …, (ca)ⁿS= (ca)^n-1caS, (ca)^n-1cbAc, (ca)^n-1cabcc= (ca)ⁿbcc. Таким образом, данная грамматика порождает язык: L(G)= {a| a= (ca)ⁿbcc}.

Две грамматики называют эквивалентными, если они порождают один и тот же язык.

Задача 2. Пусть задан некоторый язык. Построить грамматику, порождающую данный язык.

L= {aab, babaa, ababab}

R₁: S®aab, S®babaa, S®ababab; G₁= {{a, b}, {S}, S, R₁}

R₂: S®aA; S® BBa; S®AAA; A®ab;B®ba; G₂= {{a ,b}, {S, A, B}, S, R₂}.

Состав программного обеспечения ПЭВМ. Общие принципы классификации операционных систем. Понятие процессов и потоков. Дисциплины диспетчеризации.

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

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

Основные эл. системного ПО: Операционные системы - это комплекс взаимосвязанных системных программ, назначение которого — организовать взаимодействие пользователя с компьютером и выполнение всех других программ.Операционная система не только предоставляет пользователям и программистам удобный интерфейс к аппаратным средствам компьютера, но и является механизмом, распределяющим ресурсы компьютера; Драйверы – нужны для подключения устройств; Утилиты - программы, предназначенные для решения узкого круга вспомогательных задач и т.д.

Виды и классификация ОС: 1) Кол-во одновременно обслуживаемых системой пользов-лей (одно-, многопользовательские). 2)По числу процессов, одновременно выполняемых (одно-, многозадачные). 3)По типу доступа пользов-лей к ПЭВМ: -сист.с пакетной обработкой; -сист.разделения времени; -сист.реального времени; 4)По типу средств вычислит.техники для управления ресурсами которой система предназначена: -одно/многопроцессорные; -сетевые; -распределенные («облачные»); 5) Разрядность: 16-разрядная - 32-разрядная - 64-разрядная; 6) По ур. безопасности (-низкий, -высокий); 7) открытые (с возможностью редактировать исходный код) - закрытые (без возможности редактировать исходный код); 8) графические - текстовые (только командная строка);

Ресурс – это всякий объект, кот. может распределяться внутри системы.

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

Многозадачность — это способ организации вычислительного процесса, при котором на одном процессоре попеременно выполняются сразу несколько прог. Эти прог. совместно используют не только процессор, но и другие ресурсы компьютера: оперативную и внешнюю память, устройства ввода-вывода, данные. Повышает эффективность использования вычислительной системы. Наиболее характерными критериями эффективности вычислительных систем являются: пропускная способность - количество задач, выполняемых вычислительной системой в единицу времени; удобство работы пользователей, заключающееся, в частности, в том, что они имеют возможность интерактивно работать одновременно с несколькими приложениями на одной машине; реактивность системы - способность системы выдерживать заранее заданные интервалы времени между запуском программы и получением результата.

Понятие процессов и потоков: Процесс - это динамический объект, возникающий в ОС после того, как польз. или сама ОС решает "запустить программу на выполнение", то есть создать новую единицу вычислительной работы (программа в стадии выполнения). Процесс можно рассматривать также как единицу работы для процессора. Для современных типов процессоров существует и более мелкая единица работы поток (подпроцесс), т.е. прог. модули, исполняющие длительные опер., можно оформить в виде подпроцессов, вып-ся параллельно с другими подпроц. в рамках одного приложения. Потоки, как и процессы могут порождать потоки –потомки.

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

Диспетчеризация– задача динамического планирования, т.е. текущего, наиболее эффективного распределения рес., возникающего почти при каждом событии.

Планирование вып-ся раз в неск. мин., диспетчеризация может запускаться каждые 30 или 100 мс.

Дисциплины диспетчеризации:

· Бесприоритетные:1) линейные (в порядке очереди, или случайный выбор процесса). 2)циклические (циклический алгоритм, или многоприоритетный циклический алгоритм).

· Приоритетные: 1)с фиксированным приоритетом (с относительным; с абсолютным; или адаптивное обслуживание). 2) с динамическим приоритетом (адаптивное обслуживание; приоритет зависит от времени ожидания; приоритет зависит от времени обслуживания)

Дисциплины:

· FCFS – первый пришел – первый обслужен («+»: простота реализации;«­­–»: рост времени простоя при решении объемных задач).

· SJN – кратчайшее задание – вып-ся следующим, но должно быть указано время выполнения задачи.

· SRT – следующее задание, то – которое требует меньше времени для завершения.

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

Эти дисциплины делятся на:

· Не вытесняющую многозадачность. (без перераспределения процессорного времени).FCFS, SJN, SRT.

· Вытесняющая многозадачность. (с перераспределением процессорного времени). RR. Реализована в большинстве современных ОС (WindowsNT, Linux, OS/2).

Интерфейс Virtual Memory.

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

Блок адресов адресного пространства процесса может нах-ся в одном из состояний:

-выделен (commited) – блоку адресов назначена физическая память, либо часть файла подкачки

-зарезервирован (reserved) – блок адресов помечен как занятый, но физическая память не распределена

-свободен (free) – блок адресов не выделен и не зарезервирован

При выделении память обнуляется.

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

VirtualAlloc () – выделяет память. Его параметры определяют: размер выделяемой памяти (не более 1 Гб), где в адресном пр-ве расположить выделенный фрагмент, надо ли закреплять физическую память, вид устанавливаемой защиты. Резервирует память фрагментами 64 кб, а закрепляет ее фрагментами объемом 1 страницу (4 кб).

VirtualProtect() –позволяет изменять атрибуты защиты в адресном пространстве текущего процесса.

VirtualProtectEx() –позволяет изменять атрибуты защиты в адресном пространстве произвольного процесса.

VirualQuery() – заполняет поля структуры информацией о заданном блоке памяти.

GlobalMemoryStatus() – определяет размер и свободный объем физической памяти, страничного файла и текущего адресного пространства.

GetSystemInfo() – возвращает размер системной физической страницы.

Страницы можно блокировать в памяти (запрет на их вытеснение в файл подкачки) VirtualLock(), VirtualUnlock().

По завершении процесса ОС отменяет блокировку, освобождает использованную им память.

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

Интерфейс Heap Memory.

HeapMemoryAPI – набор ф-ий, позволяющих работать с динамически распределяемыми областями памяти (кучами).

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

Причины группировки выделенных блоков:

-позволяет отделить и защитить группу связанных блоков.

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

-объекты памяти, работающие совместно могут быть сгруппированы => подкачка страниц сводится к минимуму.

GetProcessHeap() – получить дескриптор стандартной кучи (по умолчанию) памяти.

HeapCreate() – создает кучу. В параметрах указывается начальный размер кучи и максимальный размер кучи (если он =0, то размер кучи ограничивается объемом доступной памяти).

HeapAlloc() – выделение блоков памяти из кучи.

HeapReAlloc() – повторное выделение…(изменение размера блока, после его выделения).

HeapFree() – освобождение блоков памяти.

HeapSize() –узнать точный размер любого блока.

HeapDestroy() – уничтожение «кучи».

Основы организации ввода-вывода в современных операционных систем. Понятие файловой системы и системы управления файлами. Синхронный и асинхронный ввод-вывод. Основные API-функции для организации ввода-вывода в ОС Windows.

Архитектура СУБД.

Основное назначение - обеспечение независимости от данных. Это значит, что изменения на нижних уровнях никак не влияют на верхние уровни.

Типы независимости от данных: 1)логическая (означает полную защищенность внешних схем от изменений, вносимых в концептуальную схему). 2)физическая(защищенность концептуальной схемы от изменений, вносимых во внутреннюю схему).

На внешнем уровне пользователи воспринимают данные. Каждый тип пользователей может применять для работы с БД свой язык общения(конечные пользователи – формы, готовые функции и запросы, а прикладные программисты языки C, Pascal, sql).

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

Внутренняя схема описывает физическую реализацию базы данных и предназначена для достижения оптимальной производительности и обеспечения экономного использования дискового пространства. На внутреннем уровне осуществляется взаимодействие СУБД с методами доступа ОС с целью размещения данных на запоминающих устройствах, создания индексов, извлечения данных. На этом уровне хранится информация: распределение дискового пространства для хранения данных и индексов, описание подробностей сохранения записей (размеры), сведения о размещении записей, сведения о сжатии данных и выбранных методов их шифрования.

Ниже находится физический уровень, контролируется операционной системой, но под руководством СУБД. Физический уровень учитывает, каким образом данные будут представлены в машине.

Реализация трехуровневой архитектуры БД требует, чтобы СУБД переводила информацию с одного уровня на другой, то есть преобразовывала адреса и указатели в соответствующие логические имена и отношения и наоборот. Выгодой такого перевода является независимость логического и физического представления данных, но и плата за эту независимость не малая — большая системная задержка.

Правил Кодда.

Правило 1. Основное правило (Foundation Rule): Реляционная СУБД должна быть способна полностью управлять базой данных, используя связи между данными.

Правило 2. Явное представление данных (The Information Rule):Информация должна быть представлена в виде данных, хранящихся в ячейках. Данные, хранящиеся в ячейках, должны быть атомарны. Порядок строк в реляционной таблице не должен влиять на смысл данных.

Правило 3. Гарантированный доступ к данным (Guaranteed Access Rule):Доступ к данным должен быть свободен от двусмысленности. К каждому элементу данных должен быть гарантирован доступ с помощью комбинации имени таблицы, первичного ключа строки и имени столбца.

Правило 4. Полная обработка неизвестных значений (Systematic Treatment of Null Values): Неизвестные значения NULL, отличные от любого известного значения, должны поддерживаться для всех типов данных при выполнении любых операций.

Правило 5. Доступ к словарю данных в терминах реляционной модели (Active On-Line Catalog Based on the Relational Model): Словарь данных должен сохраняться в форме реляционных таблиц, и СУБД должна поддерживать доступ к нему при помощи стандартных языковых средств, тех же самых, которые используются для работы с реляционными таблицами, содержащими пользовательские данные.

Правило 6. Полнота подмножества языка (Comprehensive Data Sublanguage Rule): Система управления реляционными базами данных должна поддерживать хотя бы один реляционный язык, который: а) имеет линейный синтаксис, б) может использоваться как интерактивно, так и в прикладных программах, в) поддерживает операции определения данных, определения представлений, манипулирования данными (интерактивные и программные), ограничители целостности, управления доступом и операции управления транзакциями (begin, commit и rollback).

Правило 7. Возможность модификации представлений (View Updating Rule): Каждое представление должно поддерживать все операции манипулирования данными, которые поддерживают реляционные таблицы: операции выборки, вставки, модификации и удаления данных.

Правило 8. Наличие высокоуровневых операций управления данными (High-Level Insert, Update, and Delete): Операции вставки, модификации и удаления данных должны поддерживаться не только по отношению к одной строке реляционной таблицы, но по отношению к любому множеству строк.

Правило 9. Физическая независимость данных (Physical Data Independence): Приложения не должны зависеть от используемых способов хранения данных на носителях, от аппаратного обеспечения компьютеров, на которых находится реляционная база данных.

Правило 10. Логическая независимость данных (Logical Data Independence): Представление данных в приложении не должно зависеть от структуры реляционных таблиц. Если в процессе нормализации одна реляционная таблица разделяется на две, представление должно обеспечить объединение этих данных, чтобы изменение структуры реляционных таблиц не сказывалось на работе приложений.

Правило 11. Независимость контроля целостности (Integrity Independence):Вся информация, необходимая для поддержания целостности, должна находиться в словаре данных. Язык для работы с данными должен выполнять проверку входных данных и автоматически поддерживать целостность данных.

Правило 12. Дистрибутивная независимость (Distribution Independence): База данных может быть распределённой, может находиться на нескольких компьютерах, и это не должно оказывать влияние на приложения. Перенос базы данных на другой компьютер не должен оказывать влияния на приложения.

Правило 13. Согласование языковых уровней (The Nonsubversion Rule):

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

Команды DDL.

CREATE TABLE – Создает новую таблицу в БД.

DROP TABLE – Удаляет таблицу из БД.

ALTER TABLE – Изменяет структуру существующей таблицы или ограничения целостности, задаваемые для данной таблицы.

CREATE VIEW – Создает виртуальную таблицу, соответствующую некоторому SQL-запросу.

ALTER VIEW – Изменяет ранее созданное представление.

DROP VIEW – Удаляет ранее созданное представление.

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

DROP INDEX – Удаляет ранее созданный индекс.

Команды DML.

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

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

UPDATE ­– Обновляет значения одного или нескольких столбцов в одной или нескольких строках, соответствующих условиям фильтрации.

Команды DQL.

SELECT – Оператор, заменяющий все операторы реляционной алгебры и позволяющий сформировать результирующее отношение, соответствующее запросу.

Виды нормальных форм.

С точки зрения нормализации, существует 6 нормальных форм, но на практике обычно используется только три:

первая нормальная форма (1NF): Отношение находится в 1NF, если оно удовлетворяет двум условиям:1.Значения всех его атрибутов атомарны;2.Отсутствуют повторяющиеся группы атрибутов.

вторая нормальная форма (2NF): Отношение находится в 2NF, если оно находится в 1NF и каждый неключевой атрибут функционально полно зависит от ключа.

третья нормальная форма (3NF): Отношение находится в 3NF, если оно находится в 2NF и каждый неключевой атрибут нетранзитивно зависит от первичного ключа.

нормальная форма Бойса-Кодда (BCNF):

четвертая нормальная форма (4NF):

пятая нормальная форма, или нормальная форма проекции-соединения (5NF или PJ/NF):

Построение ER-диаграммы.

Чаще всего концептуальная модель представляется в виде диаграммы сущностей – связей (entity – relationship) или ER-диаграммы. Процесс построения ER-диаграммы называется ER-моделированием. Сущность (Entity) или объект – то, о чем будет накапливаться информация в информационной системе (нечто такое, за чем пользователь хотел бы наблюдать).

Процедуры моделирования.

Стадия 1 – начало работы над проектом: Разрабатывается план моделирования, в котором указываются задания для выполнения и последовательность, в которой они должны выполняться.

Стадия 2 – определение сущностей:

Стадия 3 – определение отношений:

Стадия 4 – определение ключей: Цели стадии: 1)Детализация неспецифических отношений; 2)Определение ключевых атрибутов для каждой сущности; 3)Перемещение первичных ключей на установление внешних ключей; 4)Проверка правильности ключей и отношений.

Стадия 5 – определение атрибутов: Цели стадии: 1)Установление принадлежности атрибутов к сущности; 2)Определение не ключевых атрибутов; 3)Проверку правильности и детализацию структур данных.

Имя атрибута должно быть уникальным.

Пример диаграммы.

Машина Тьюринга.

Машина Тьюринга (МТ) — математическая абстракция, представляющая вычислительную машину общего вида. Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.

Машина Тьюринга является расширением модели конечного автомата и, согласно тезису Чёрча — Тьюринга, способна имитировать (при наличии соответствующей программы) любую машину, действие которой заключается в переходе от одного дискретного состояния к другому.

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

Машина Тьюринга представляет собой: бесконечную в обе стороныленту, разделённая на ячейки, и управляющее устройство(конечный автомат)с конечным числом состояний, и коретку.

Составляющие машины: 1)Внешний алфавит. Конечное множество (например, А), элементы которого называются буквами (символами). Одна из букв этого алфавита (например, а₀) должна представлять собой пустой символ. 2)Внутренний алфавит. Конечное множество состояний головки (автомата). Одно из состояний (например, q₁) должно быть начальным (запускающим программу). Еще одно из состояний (q₀) должно быть конечным (завершающим программу) – состояние останова. 3)Таблица переходов. Описание поведения автомата (головки) в зависимости от состояния и считанного символа.

Управляющее устройство может перемещаться влево и вправо по ленте, читать и записывать в ячейки символы некоторого конечного алфавита. Выделяется особый пустой символ, заполняющий все клетки ленты, кроме тех из них (конечного числа), на которых записаны входные данные.

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

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

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

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

Пример реализации машины Тьюринга.

Наращиваемую память в современных ЭВМ можно считать аналогом бесконечной в одну сторону рабочей ленты машины Тьюринга. Причём достаточно только пяти типов команд чтобы реализовать операции машины Тьюринга: 1)сдвиг{влево,вправо}–Сдвиг головки на 1 позицию на ленте влево или вправо; 2)переход,р– Безусловный переход к команде с номером р. 3) если,s,р– Условный переход к команде с номером р, если в обозреваемой ячейке находится символ s;4)печать, s– Печать символа sв обозреваемую ячейку; 5)стоп– Остановка.

Например, начало программы машины Тьюринга, которая находит НОД, имеет вид:

00: если, а, 02;{если в начальном состоянии прочитан символа, то на команду 02}

01: переход, 05;{если нет, то на проверку другого символа}

02: печать, а;

03: сдвиг, влево;

04: переход,00;{возврат в начальное состояние}

05: если, b, 07; {если в начальном состоянии прочитан символ b,

то на команду 07}

06:переход, 10; {если нет, то на проверку другого символа}

07:печать,b;

08:сдвиг,влево;

09:....

Машина Поста.

Машина Поста – это абстрактная (несуществующая реально) вычислительная машина, созданная для уточнения (формализации) понятия алгоритма. Представляет собой универсальный исполнитель, позволяющий вводить начальные данные и читать результат выполнения программы.В 1936 г. американский математик Эмиль Пост в статье описал систему, обладающую алгоритмической простотой и способную определять, является ли та или иная задача алгоритмически разрешимой. Если задача имеет алгоритмическое решение, то она представима в форме команд для машины Поста.

Машина Поста состоит из : 1)бесконечной ленты, поделенной на одинаковые ячейки (секции). Ячейка может быть пустой (0 или пустота) или содержать метку (1 или любой другой знак); 2)головки (каретки), способной передвигаться по ленте на одну ячейку в ту или иную сторону, а также способной проверять наличие метки, стирать и записывать метку.

Текущее состояние машины Поста описывается состоянием ленты и положением каретки. Состояние ленты – информация о том, какие секции пусты, а какие отмечены. Шаг – это движение каретки на одну ячейку влево или вправо. Состояние ленты может изменяться в процессе выполнения программы. Кареткой управляет программа, состоящая из строк команд. Каждая команда имеет следующий синтаксис: i K j,, где i - номер команды, K – действие каретки, j - номер следующей команды (отсылка).

Всего для машины Поста существует шесть типов команд: 1)V j - поставить метку, перейти к j-й строке программы; 2)X j - стереть метку, перейти к j-й строке программы;3)<- j - сдвинуться влево, перейти к j-й строке программы; 4) -> j - сдвинуться вправо, перейти к j-й строке программы; 5)? j₁; j₂ - если в ячейке нет метки, то перейти к j₁-й строке программы, иначе перейти к j₂-й строке программы; 6)! – конец программы (стоп).

У команды «стоп» отсылки нет.

Варианты окончания выполнения программы на машине Поста: 1)Команда "стоп" - корректная остановка. Возникает в результате выполнения правильно написанного алгоритма;2)Выполнение недопустимой команды – нерезультативная остановка. Случаи, когда головка должна записать метку там, где она уже есть, или стереть метку там, где ее нет, являются аварийными (недопустимыми);3)Уход в бесконечность, зацикливание. Машина Поста в результате работы алгоритма может вообще не остановиться (никогда не дойти до команды «стоп» и никогда не завершиться аварийной ситуацией).

Элементарные действия (команды) машина Поста проще команд машины Тьюринга. Поэтому программы для машины Поста имеют большее число команд, чем аналогичные программы для машины Тьюринга.Машина Поста имеет лишь два различных символа (есть метка, нет метки). Т.к любой алфавит может быть закодирован двумя знаками; в зависимости от алфавита возрастать может только количество двоичных символов в букве алфавита.

Пример работы машины Поста:

Задача: увеличить число 3 на единицу (изменить значение в памяти с 3 на 4).
Целое положительное число на ленте машины Поста представимо идущими подряд метками, которых на одну больше, чем кодируемое число. Это связано с тем, что одна метка обозначает ноль, а уже две – единицу, и т.д.
Допустим, точно известно, что каретка стоит где-то слева от меток и обозревает пустую ячейку. Тогда программа увеличения числа на единицу может выглядеть так:
1 -> 2
2 ? 1;3
3 <- 4
4 V 5
5 !

Алгоритм Маркова.

Нормальный алгоритм описывает метод переписывания строк, похожий по способу задания на формальные грамматики. НАМ является Тьюринг полым языком (т.е. исполнителем на котором можно реализовать любую вычислимую функцию), что делает его по выразительной силе эквивалентным машине Тьюринга и, следовательно, современным языкам программирования. На основе НАМ был создан функциональный язык программирования Рефал. Нормальным алгоритмом Маркова (НАМ) называется непустой конечный упорядоченный набор формул подстановки: α₁ → β₁, α₂ → β₂,…, α_k → β_k.( k ≥ 1 ). В этих формулах могут использоваться два вида стрелок: обычная стрелка (→), обычная формула, и формула со стрелкой «с хвостиком» – заключительная формулой.

Сама подстановка (как действие) задается формулой подстановки и применяется к некоторому слову Р. Суть операции сводится к тому, что в слове Р отыскивается часть, совпадающая с левой частью этой формулы (т.е. с α), и она заменяется на правую часть формулы (т.е. на β). При этом остальные части слова Р (слева и справа от α) не меняются. Получившееся слово R называют результатом подстановки. Это можно изобразить так: .

Для формализации понятия алгоритма российский математик А.А.Марков предложил использовать ассоциативные исчисления. Рассмотрим некоторые понятия ассоциативного исчисления. Пусть имеется алфавит (конечный набор различных символов). Составляющие его символы будем называть буквами. Любая конечная последовательность букв алфавита (линейный их ряд) называется словом в этом алфавите.

Рассмотрим два слова N и М в некотором алфавите А. Если N является частью М, то говорят, что N входит в М.

Зададим в некотором алфавите конечную систему подстановок N - М, S - Т,..., где N, М, S, Т,... - слова в этом алфавите. Любую подстановку N-M можно применить к некоторому слову К следующим способом: если в К имеется одно или несколько вхождений слова N, то любое из них может быть заменено словом М, и, наоборот, если имеется вхождение М, то его можно заменить словом N.

Например, в алфавите А = {а, b, с} имеются слова N = ab, М = bcb, К = abcbcbab, Заменив в слове К слово N на М, получим bcbcbcbab или abcbcbbcb, и, наоборот, заменив М на N, получим aabcbab или аbсаbаb.

Подстановка ab - bcb недопустима к слову bacb, так как ни ab, ни bcb не входит в это слово. К полученным с помощью допустимых подстановок словам можно снова применить допустимые подстановки и т.д. Совокупность всех слов в данном алфавите вместе с системой допустимых подстановок называют ассоциативным исчислением. Чтобы задать ассоциативное исчисление, достаточно задать алфавит и систему подстановок.

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

Способы композиции нормальных алгоритмов: 1)Суперпозиция алгоритмов. При суперпозиции двух алгоритмов А и В выходное слово первого алгоритма рассматривается как входное слово второго алгоритма В. Результат суперпозиции С может быть представлен в виде С(р) = В(А(р));

2) Объединение алгоритмов. Объединением алгоритмов А и В в одном и том же алфавите называется алгоритм С в том же алфавите, преобразующий любое слово р, содержащееся в пересечении областей определения алгоритмов А и В, в записанные рядом слова А(р) и В(р); 3)Разветвление алгоритмов. Разветвление алгоритмов представляет собой композицию D трех алгоритмов А, В и С, причем область определения алгоритма D является пересечением областей определения всех трех алгоритмов А, В и С, а для любого слова р из этого пересечения D(p) = А(р), если С(р) = е, D(p) = B(p), если С(р) = е, где е - пустая строка; 4)Итерация алгоритмов. Итерация (повторение) представляет собой такую композицию С двух алгоритмов А и В, что для любого входного слова р соответствующее слово С(р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В.

Рекурсивные функции.

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

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

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

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

Гёдель впервые описал класс всех рекурсивных функций как класс всех числовых функций, определимых в некоторой формальной системе. Исходя из совершенно других предпосылок, Черч в 1936 г. вывел тот же класс числовых функций, что и Гёдель. Черчем была сформулирована гипотеза. Числовая функция тогда и только тогда алгоритмически вычислима, когда она рекурсивна. Эта гипотеза известна под именем тезиса Черча. Понятие вычислимой функции точно не определяется, поэтому тезис Черча доказать нельзя. Клини ввел понятие частично рекурсивной функции и высказал гипотезу: что все частичные функции, вычислимые посредством алгоритмов, являются частично рекурсивными. Гипотеза Клини также недоказуема, как и гипотеза Черча. Однако математические исследования последних 30 лет выявили полную целесообразность считать понятие частично рекурсивной функции научным эквивалентом интуитивного понятия вычислимой частичной функции.

[1]

Определение грамматики. Понятие грамматики. Виды грамматики.

Грамматика – описание спос