Переход от автомата Мили к автомату Мура.

qixj ® yij bij Т.П.	q1/b0	q2	q3
x1	q1/b11	q3/b21	q2/b31
x2	q2/b12	q1/b22	q3/b32

 

Т.В.	q1	q2	q3
x1	y3	y1	y2
x2	y4	y5	y6

 

		y3	y4	y1	y5	y2	y6
	b0	b11	b12	b21	b22	b31	b32
x1	b11	b11	b21	b31	b11	b21	b31
x2	b12	b12	b22	b32	b12	b22	b32

 

Теорема: (Глушкова)

Таким образом доказана конструктивная теорема, что для произвольного автомата Милли может быть

построен эквивалентный ему автомат Мура имеющий не более

n * m + 1 состояний, где n - число входных сигналов, m - число состояний исходного автомата Милли.

 

Распознающие автоматы.

Распознающим называется автомат Мура с множеством выделенных состояний, называемых конечными.

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

он заканчивает ее в одном из конечных.

Пример: Автомат, распознающий слова содержащие попарное вхождение букв а

и b, вроде aabbbbaa. f1, f2 - конечные состояния

Распознающий автомат – это, как правило,

недетерминированный частичный автомат.

То есть по одному и тому же сигналу можно

перейти в различные состояния, а в некоторых

состояниях нет перехода для ряда входных

сигналов.

 

 

	A	B	C	F
a	B,C		F
b	B	С,F

 

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

Представление этого автомата с помощью автоматной грамматики:

A ® aB | bB | aC

B ® bC | b

C ® a

Это праворекурсивная автоматная грамматика.

 

Понятие предиката.

Предикат - логическая функция, аргументы которой могут принимать значения из некоторой предметной

функции, а сама функция может принимать значение истина либо ложь.

Если переменная одна, то предикат одноместный, две - двухместный и т.д.

Нульместный предикат, то есть предикат, не содержащий переменных - высказывание.

Операции:

Из элементарных (атомарных) предикатов с помощью логических операций можно получить сложные

предикаты.

Здесь уместно сделать важное содержательное замечание:

Язык предикатов - наиболее приближенный к естественным языкам формальный математический

(логический) язык.

В логике предикатов к операциям, имеющим место в логике высказываний, добавляются операции

навешивания кванторов.

" - квантор общности. "x P(x) - "для всех х - P(x)".

$ - квантор существования. $x P(x) - "есть такие х, что P(x)".

($! или $₁ - существует и притом единственный).

Кванторы связывают соответствующие переменные. Связанные переменные можно воспринимать как

константы, а несвязанные переменные - свободные переменные -

как собственно переменные.

Содержательные примеры предикатов:

R(x) - х любит кашу (одноместный предикат).

"x R(x) - все любят кашу (нульместный предикат - высказывание).

$x R(x) - некоторые (есть такие) х любят кашу.

L(x, y) - х любит y (двухместный предикат).

$x"y L(x, y) - Существует x, который любит всех y.

"x (C(x) ® O(x)) - Все студенты C(x) отличники O(x).

$x (C(x) & O(x)) - Некоторые студенты C(x) отличники O(x).

Здесь есть повод поразмышлять об использовании операций ® и & в двух последних высказываниях.

Для конечных областей можно операции навешивания кванторов выразить через конъюнкцию и

дизъюнкцию:

Пусть х Î{a₁, a₂,..., a_n}

"x P(x) = P(a₁) & P(a₂) &... & P(a_n).

$x P(x) = P(a₁) Ú P(a₂) Ú... Ú P(a_n).