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

Т.В.	q₁	q₂	q₃
x₁	y₃	y₁	y₂
x₂	y₄	y₅	y₆

		y₃	y₄	y₁	y₅	y₂	y₆
	b₀	b₁₁	b₁₂	b₂₁	b₂₂	b₃₁	b₃₂
x₁	b₁₁	b₁₁	b₂₁	b₃₁	b₁₁	b₂₁	b₃₁
x₂	b₁₂	b₁₂	b₂₂	b₃₂	b₁₂	b₂₂	b₃₂

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

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

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

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).