Переход от автомата Мили к автомату Мура.
| 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).