Теория конечных автоматов

Построить булеву функцию f, описывающую поведение лампочки контактной структуры

Задача 1

Построить булеву функцию f, описывающую поведение лампочки контактной структуры, изображенной на рисунке:

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

Решение:

Функция f имеет вид .

Если замкнуть контакт А, то реакция будет соответствовать функции

. Лампочка будет гореть постоянно.

Задача 2

Равны ли логические структуры контактных групп, изображенных на рисунках:

Решение:

Первая логическая схема соответствует уравнению:

Вторая:

Составим таблицы истинности для первого: a'b'c'd'f 0'0'0'0'1 0'0'0'1'1 0'0'1'0'1 0'0'1'1'1 0'1'0'0'0 0'1'0'1'1 0'1'1'0'1 0'1'1'1'1 1'0'0'0'0 1'0'0'1'1 1'0'1'0'0 1'0'1'1'0 1'1'0'0'0 1'1'0'1'1 1'1'1'0'1 1'1'1'1'1

Для второй: a'b'c'd'f 0'0'0'0'1 0'0'0'1'0 0'0'1'0'0 0'0'1'1'0 0'1'0'0'1 0'1'0'1'0 0'1'1'0'1 0'1'1'1'1 1'0'0'0'1 1'0'0'1'0 1'0'1'0'1 1'0'1'1'1 1'1'0'0'1 1'1'0'1'0 1'1'1'0'1 1'1'1'1'1

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

Задача 3

Найти минимальную контактную структуру, работающую согласно условиям: A, B, C, D управляют лампочкой; лампочка горит, если одновременно нажаты кнопки B и C, а кнопка A не нажата.

Решение:

Логическая функция f имеет вид:

Минимальная контактная структура имеет вид:

Задача 4

Задана машина Тьюринга таблицей переходов по состояниям:

Проверить: в какое слово перерабатывает эта машина слово 111*11 (если машина работает бесконечно, то выходным словом считать а0).

Решение:

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

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

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

Задача 5

Сконструировать машину Тьюринга, которая бы два конечных набора m и n единиц (m≥n), разделённых * подвергала преобразованию вида: в левом наборе остаётся ровно столько единиц, на сколько в левом наборе их больше, чем в правом; остальные единицы стираются (вычитание).

Решение:

Рассмотрим задачу сложения двух натуральных чисел. Представим натуральные числа в единичном (унарном) коде, например, для числа х справедливо 1…1=1х. Положим, что для всех числовых функций Аисх='1' либо Аисх='1,*'.

Тогда числовая функция f(х1, …, хn) правильно вычислима по Тьюрингу, если существует машина Тьюринга такая, что

, когда f(х1, …, хn)=у, и машина Тьюринга работает бесконечно, начиная с , когда f(х1, …, хn) не вычислима.

Рассмотрим вычитание 2 чисел a и b (Аисх=1a•1b), это слово необходимо переработать в 1a-b.

Это преобразование осуществляет машина Т+ с 4 состояниями.

В табличной форме программа управления выглядит так: А Q'q1'q2'q3'q4 а0'q1а0П'q3а0П'q3а0Л'q1а0Л 1'q2а0Л'q21Л'q4а0П'q41П *'q0а0'q3*Л q4*П


Способ заказа и контакты