29. Вычислительная мощность мт.

Любое вычислительное устройство может имитировать работу МТ и наоборот. Время работы зависит полиноминально.

Для имитации МТ на компьютере следует использовать язык высокого уровня (последовательности, выбор, циклы).

Основная теорема структурного программирования: Компьютер может быть имитирован многоленточной МТ.

Свойства МТ

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

Для любой МТ существует эквивалентная МТ, работающая на полубесконечной ленте.

Проблему называют алгоритмически разрешимой, если существует

машина Тьюринга, решающая любую индивидуальную задачу из этой

проблемы (т.е. переводящая за конечное число шагов начальные данные

на ленте в правильный ответ). В противном случае проблему называют алгоритмически неразрешимой.

Алгоритмически не разрешимые проблемы:

Основной постулат: Не существует алгоритм, позволяющий на основании описания алгоритма и его исходных данных определить, конечен он или нет.

Разрешимые проблемы:

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

2. Множество цепочек, принимаемых конечным автоматом с n состояниями,

   1. не пусто тогда и только тогда, когда он принимает цепочку длиной, меньше n;

   2. бесконечно тогда и только тогда, когда он принимает цепочку длиной l, n ≤ l < 2n

Не разрешимые проблемы:

1. Проблема эквивалентности алгоритмов: по двум произвольны заданным алгоритмам определить, будут ли они выдавать одинаковые выходные результаты на любых исходных данных.

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

3. Проблема тотальности: по произвольному заданному алгоритму определить, будет ли он завершаться (останавливаться) на всевозможных входных наборах

4. Проблема Гильберта (Не существует алгоритма, который по заданному многочлену Р=(х₁, …, х_n) с целым коэффициентами определил имеет ли полином Р=0 решение в целых корнях)

5. Проблема соответствия Поста. (Пусть мы имеем набор пар цепочек (A,B), (A₂,B₂), существует ли такое целое P>0, для которого цепи вида А₁, …, А_ip, и В₁, …, В_ip, совпадают)

31. Регулярные выражения (рв) и языки. Операторы рв. Приоритеты операторов. Связь рв, дка, ε-нка, нка.

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

1. Объединение двух языков L и M, - это множество цепочек содержащихся либо в L, либо в M, либо в обоих языках.

2. Конкатенация языков L и M, LM - это множество цепочек, которое можно образовать путем дописывания к любой цепочке из L любой цепочки из M

3. Итерация (звездочка или замыкание Клини) языка L обозначается L^* и представляет собой множество всех тех цепочек, которые можно образовать путем конкатенации любого количества цепочек из L.

Алгебра регулярных выражений строится аналогично обычной:

ε и являются регулярными выражениями языков {ε} и {

Существуют приоритеты:

Высокий *; ниже конкатенация, еще ниже объединение.

Любой язык заданный ДКА, НКА, ε-НКА может быт задан регулярным выражением. Любой регулярный язык может быть реализован этими автоматами.