русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Понятие автомата.


Дата добавления: 2015-07-23; просмотров: 785; Нарушение авторских прав


Понятие алгоритма вводилось до сих пор чисто интуитивно. Понятие автомата позволяет уточнить понятие алгоритма. А это, в свою очередь, позволяет решить вопрос об алгоритмической разрешимости той или иной проблемы. В частности с помощью машины Тьюринга американским ученым Черчем (1903-1992) был получен результат при решении проблемы распознавания выводимости в математической логике: для любых заданных формул R и S в логическом исчислении определить существует ли дедуктивная цепочка, ведущая от R к S или нет.

Теорема Черча.

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

Автоматы, изучаемые в последующих разделах, можно рассматривать как механизмы, состоящие из блока управления, который может пребывать в различных состояниях (внутренние состояния автомата), а также входного и выходного каналов. Входной канал воспринимает (считывает) сигналы из внешней среды, а выходной канал выдает сигналы во внешнюю среду. Природа состояний и сигналов безразлична, их можно рассматривать как некоторые символы (буквы), образующие соответственно алфавит состояний (или внутренний алфавит) – Q, входной алфавит – X, и выходной алфавит – Y. Каждая команда может быть записана в виде

(*)

где qi , qjвнутренние состояния автомата, xr – входной символ, уs – выходной символ.

Пусть на некотором такте t0 блок управления установлен в состояние qi, и входной канал воспринимает символ xr. Если в программе имеется команда (*), то в этом же такте выходной канал выдает символ xr, а к следующему такту t0 + 1 блок управления перейдет в состояние qj . Если такой команды нет, то автомат блокируется. В этом и заключается функционирование автомата. Множество внутренних состояний автомата является его внутренней памятью.

Таким образом, автомат – это пятерка (Q, X, Y, Ψ, Φ), где Q, X, Y – алфавиты, Ψ – функция переходов отображение Q X в Q, Φ – функция выходов (отображение Q X в Y). Пусть зафиксировано некоторое состояние автомата. Тогда рекуррентные соотношения



где q(t), q(t + 1) Q, x(t) X, y(t) Y, дополненные начальным условием q(1) = q0, задают оператор T, который преобразует всякую конечную последовательность входящих символов

x = x(1) x(2) ...x(r) в некоторую последовательность выходных символов

y = Tx = y(1) y(2) .... y(r) .



<== предыдущая лекция | следующая лекция ==>
Задача о кратчайших путях. | Машина Тьюринга.


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.005 сек.