Студопедия — Функционирование НАМ
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Функционирование НАМ






1. , – номер подстановки в схеме НАМ.

2. Выбирается -тая МП, пусть она имеет вид

3. Левая часть подстановки ищется в преобразуемом слове .

4. Если найдено, то переход к пункту 7, иначе к пункту 5.

5.

6. Если не превышает общего числа подстановок, то переход к пункту 2, иначе – алгоритм заканчивает работу, останавливается.

7. Выполняется замена на в преобразуемом слове (крайнее левое вхождение в ).

8. Если эта подстановка является заключительной, т.е. имеет вид , алгоритм останавливается, иначе переход к пункту 1.

После применения подстановки осуществляется заново просмотр столбца подстановок, а не продолжается просмотр .

Процесс заканчивается, если:

- не найдена применяемая подстановка;

- выполнена заключительная подстановка.

Алфавит называется расширением алфавита , если .

Нормальный алгоритм над алфавитом – это нормальный алгоритм в алфавите , который слова в , если он к ним применим, перерабатывает в слова в . Нормальный алгоритм в может использовать только буквы алфавита .

Нормальный алгоритм над может использовать вспомогательные символы. НАМ над более мощные, чем НАМ в А.

Одноместная частичная словарная функция , заданная в алфавите называется нормально вычислимой, если существует НАМ над алфавитом , перерабатывающий слово в слово .

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

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

Пусть Тогда, последовательность преобразований имеет вид:

Пример 2. Нормальный алгоритм над алфавитом стирающий все символы входного слова до первого символа включительно.

Здесь вспомогательные символы и , таким образом, алфавит . Буква служит для того, чтобы найти букву 2 последовательным перебором слева направо. Буква позволяет стереть буквы движением справа налево.

Пример функционирования НАМ по переработке слова :

Пример 3. Нормальный алгоритм над алфавитом , который выдает “и”, если в исходном слове, состоящем из нулей и единиц, есть комбинация , и “л”, в противном случае.

Приведем два примера функционирования НАМ:

1)

2)

Пример 4. Пример НАМ, который работает бесконечно.







Дата добавления: 2015-09-18; просмотров: 503. Нарушение авторских прав; Мы поможем в написании вашей работы!



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

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

Функция спроса населения на данный товар Функция спроса населения на данный товар: Qd=7-Р. Функция предложения: Qs= -5+2Р,где...

Аальтернативная стоимость. Кривая производственных возможностей В экономике Буридании есть 100 ед. труда с производительностью 4 м ткани или 2 кг мяса...

Особенности массовой коммуникации Развитие средств связи и информации привело к возникновению явления массовой коммуникации...

Тема: Изучение приспособленности организмов к среде обитания Цель:выяснить механизм образования приспособлений к среде обитания и их относительный характер, сделать вывод о том, что приспособленность – результат действия естественного отбора...

Тема: Изучение фенотипов местных сортов растений Цель: расширить знания о задачах современной селекции. Оборудование:пакетики семян различных сортов томатов...

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

ПРОФЕССИОНАЛЬНОЕ САМОВОСПИТАНИЕ И САМООБРАЗОВАНИЕ ПЕДАГОГА Воспитывать сегодня подрастающее поколение на со­временном уровне требований общества нельзя без по­стоянного обновления и обогащения своего профессио­нального педагогического потенциала...

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

Studopedia.info - Студопедия - 2014-2024 год . (0.011 сек.) русская версия | украинская версия