All posts by admin

«В начале было слово…» Бытие, 1,1 Определение. ТЕОРИЯ АВТОМАТОВ – это раздел дискретной математики, изучающей математические модели дискретных преобразователей информации.

Определение. ЗНАК – это элемент конечного множества различных элементов. Пример. +,-,*

1. Операция конкатенации строк (соединение строк). Пусть заданы строки принадлежащие множеству над алфавитом .

Определение. ФОРИАЛЬНОЙ ГРАММАТИКОЙ называется формальная система, состоящая из четырех объектов , где

КЛАССИФИКАЦИЯ ГРАММАТИК ПО ХОМСКОМУ. Общепринятой классификацией грамматик и порождаемых ими языков является иерархия Хомского, содержащая четыре типа грамматик.

Формальные языки классифицируются по типу грамматики, которая их порождает, то есть язык, порожденный грамматикой типа 0, называется языком типа 0. Язык, порожденный грамматикой типа 1, называется языком типа

Для произвольной КС грамматики существует эквивалентная ей КС грамматика такая, что . То есть язык порождаемый КС грамматикой эквивалентен языку порождаемому КС грамматикой с точностью до пустой строки. Очевидно, что КС грамматика не содержит продукций вида .

Определение. ЦЕПНОЙ ПРОДУКЦИЕЙ называется продукция вида. ТЕОРЕМА 1.2. О КС грамматике без цепных продукций. Для произвольной КС грамматике содержащей цепные продукции вида , где существует эквивалентная ей КС грамматика не содержащая цепных продукций.

Определение. ДОСТИЖИМЫМ(ВЫВОДИМЫМ) нетерминальным знаком называется такой нетерминальный знак , что в грамматике существует вывод ;  

Под РАЗРЕШИМОСТЬЮ ЯЗЫКОВ понимается распознавание принадлежности произвольной строки языку, заданному формальной грамматикой .

Если — КС грамматика, то разрешима проблема пустоты языка . ДОКАЗАТЕЛЬСТВО. Применим к КС грамматике эффективную процедуру приведения КС грамматики. Если получена КС грамматика у которой аксиома — производящий знак, то язык не пуст. В противном случае язык пуст.

Определение. НЕРАЗРЕШИМОЙ ПРОБЛЕМОЙ называется отсутствие эффективной процедуры решения некоторой задачи для наперед неизвестной грамматики .

Если и КС грамматики, то неразрешимыми проблемами являются: 1. Пусто ли пересечение КС языков? То есть , или нет? 2. Является ли КС языком пересечение КС языков? То есть если и КС грамматики и , -КС язык или нет?

«Многие вещи нам не понятны не потому, что наши понятия слабы, но потому, что сие вещи не входят в круг наших понятий» К. Прутков.

Определение. МАШИНОЙ ТЬЮРИНГА называется формальная система (устройство), задаваемое четверкой объектов , где — конечный алфавит ленты,

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

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

Стоит задача определения результативности алгоритма, которая является необходимым условием для реализации. Определение. РЕЗУЛЬТАТИВНОСТЬ – есть получение результата за конечное время (конечное число шагов).

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

Никакое нетривиальное свойство вычислимых функций не является алгоритмически разрешимым.

Определение. ДАТЕРМЕНИРОВАННОЙ МАШИНОЙ ТЬЮРИНГА называется такая машина Тьюринга, у которой отображение множества декартового произведения множеств алфавита ленты и состояния устройства управления в множество декартового произведения множеств алфавита ленты, состояния устройства управления и множества перемещения ленты – функционально, то есть не существует двух одинаковых команд в множестве с одинаковой левой частью.

Сеть Петри представляет собой модель дискретных систем. Дадим неформальное определение сети Петри.

1. “Возбуждение переходов”. Те переходы, которые имеют входящие дуги от позиций, содержащих метки, возбуждаются, то есть способны к функционированию (срабатыванию). В примере возбуждаются преходы .