Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

Свойства и основные тождества




Из аксиом видно, что наименьшим элементом является 0, наибольшим является 1, а дополнение a любого элемента a однозначно определено. Для всех a и b из A верны также следующие равенства:

; ;  
; ;  
; ;
; ; дополнение 0 есть 1 и наоборот
; ; законы де Моргана
.   инволютивность отрицания

 

; . 1 коммутативность переместительность
; . 2 ассоциативность сочетательность
3.1 конъюнкция относительно дизъюнкции 3.2 дизъюнкция относительно конъюнкции 3 дистрибутивность распределительность
; . 4 комплементность дополнительность (свойства отрицаний)
; . 5 законы де Моргана
; . 6 законы поглощения
; . 7 Блейка-Порецкого
; . 8 Идемпотентность
.   9 инволютивность отрицания
; . 10 свойства констант
; .
дополнение 0 есть 1 ; дополнение 1 есть 0 .
; . 11 Склеивание

Графы и деревья

Дерево (структура данных)

Дерево — одна из наиболее широко распространённых структур данных в информатике, эмулирующая древовидную структуру в виде набора связанных узлов. Является связанным графом, не содержащим циклы. Большинство источников также добавляют условие на то, что рёбра графа не должны быть ориентированными. В дополнение к этим трём ограничениям, в некоторых источниках указываются, что рёбра графа не должны быть взвешенными.

Определения

· Корневой узел — самый верхний узел дерева.

· Корень — одна из вершин, по желанию наблюдателя.

· лист, листовой или терминальный узел — узел, не имеющий дочерних элементов.

· Внутренний узел — любой узел дерева, имеющий потомков, и таким образом не являющийся листовым узлом.

Дерево считается ориентированным, если в корень не заходит ни одно ребро.

В математической теории графов и информатике граф — это совокупность непустого множества вершин и множества пар вершин.

Объекты представляются как вершины, или узлы графа, а связи — как дуги, или рёбра. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах.


 

Лекция №3. Конечные автоматы. Машина Тьюринга и машина Поста.

 

План лекций

1. Конечные автоматы.

2. Машина Тьюринга и машина Поста.

 

 

Ключевые слова:конечные автоматы, машина Тьюринга, машина Поста, управляющее устройство, детерминированный.

Иллюстративный материал:Таблица, схема.

 

Конечные автоматы

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

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

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

  • Q — конечное множество состояний автомата;
  • q0начальное (стартовое) состояние автомата ( );
  • F — множество заключительных (или допускающих) состояний, таких что ;
  • Σ — допустимый входной алфавит (конечное множество допустимых входных символов), из которого формируются строки, считываемые автоматом;
  • δ — заданное отображение множества во множество подмножеств Q:

(иногда δ называют функцией переходов автомата).

Автомат начинает работу в состоянии q0, считывая по одному символу входной строки. Считанный символ переводит автомат в новое состояние из Q в соответствии с функцией переходов. Если по завершении считывания входного слова (цепочки символов) автомат оказывается в одном из допускающих состояний, то слово «принимается» автоматом. В этом случае говорят, что оно принадлежит языку данного автомата. В противном случае слово «отвергается».

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





Рекомендуемые страницы:

Воспользуйтесь поиском по сайту:



©2015- 2021 megalektsii.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.