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

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

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

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

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

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

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

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

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

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

дизъюнкцию:

Пусть х Î{a1, a2, ... , an}

"x P(x) = P(a1) & P(a2) & ... & P(an).

$x P(x) = P(a1) Ú P(a2) Ú ... Ú P(an).

   
 
 
 

Наши рекомендации