Лекции - Системы искусственного интеллекта
Подождите немного. Документ загружается.
Начальное состояние
Bb
0
. Обычно будем полагать, что
i
bb
0
.
В дальнейшем для простоты вместо длинного
словосочетания "инициальный детерминированный конечный
автомат" будем говорить просто "автомат". Автомат можно
рассматривать как эквивалент некоторой абстрактной среды,
которая имеет множество состояний
B
и начальное состояние
Bb
0
. Когда среда находится в каком-либо состоянии
i
b
,
агентом может быть совершено действие
a
. В результате
среда перейдёт в состояние
j
b
, которое определяется
функцией переходов
ji
bbaf ),(
. В каждом состоянии
j
b
может
быть определена функцией выходов, которая называется также
иногда оценочной функцией
ii
cb )(
. Если автомат находится в
состоянии
0
b
, то считается, что ещё никакая входная
последовательность на него не была подана. Для удобства
будем полагать, тем не менее, что на него была подана
пустая последовательность
е
.
Таким образом, автомат перерабатывает
последовательность
ilii
aaеa
21
в последовательности
ilii
bbbb
210
,
ilii
cccc
210
, где
Aaaa
ilii
,,,
21
,
Bbbbb
ilii
,,,,
210
,
Ccccc
ilii
,,,,
210
. Если на автомат была подана
последовательность
1i
еa
, то он перейдет в состояние
1i
b
и
т.д. Если на него была подана последовательность
ilii
aaеa
21
,
то он перейдёт в состояние
il
b
. Говорят при этом, что
последовательность
ilii
aaеa
21
ведёт в состояние
il
b
из
начального состояния
0
b
. Произвольную последовательность
во входном алфавите обозначим
*
a
. Если она ведёт в
некотрое состояние
j
b
из некоторого состояния
i
b
, то этот
факт записывается так:
ji
bbaf ),(
**
.
Последовательности действий подразделяют на допустимые
и запрещенные. Допустимыми называют псоледвоательности,
которые могут быть поданы на автомат, а запрещенными -
последовательности, которые на автомат никогда не подаются.
Условно считается, что все запрещенные последовательности
ведут в одно и то же фиктивное состояние
B
и
1)(
.
Функцию выходов можно определить не на всех состояниях.
Если она не определена, то будем считать, что её значение
равно
. Если при этом
j
bbaf ),(
**
0
и функция выхода
cb
j
)(
или
)(
j
b
, то этот факт запишем
ca )(
**
или
)(
**
a
соответственно.
101
15.ЯЗЫК И АВТОМАТ
Множество (алфавит)
A
назовём множеством допустимых
действий
i
aaaaa
21
*
;
произвольная, конечная или бесконечная
последовательность допустимых действий (входная
последовательность) в алфавите
*
, AA
множестов всех
последовательностей
*
a
,
e
пустое действие,
**
aea
,
*
функция на множестве
eAA
*'*'
, которая ставит в
соответствие последовательностям
*"
Aa
элементы
множества
CC"
, где
символ неопределенного
значения, т.е.
Ca
)(
**
или
*'''*''*'*
: SCAA
. Обозначим
*"
AP
множество допустимых последовательностей
действий агента, включая последовательность из одного
пустого действия
e
.
S
множество последовательностей
)(
***
aa
таких, что
Pa
*
,
Baf )(
**
;
Ca
)(
**
. очевидно, что
*
SS
.
Иначе говоря, множестов последовательностей
P
таково,
что оно состоит только из допустимых последовательностей
действий и каждая такая последовательность ведёт в какое-
либо состояние среды. Множество
S
получается из множества
P
приписыванием к концу каждой последовательности
Pa
*
элемента множества
"
C
(выходного символа), и наоборот,
множество
P
получается из множества
S
удалением у каждой
последовательности этого множества последнего символа.
Получаемое таким образом множество
P
по множеству
S
обозначается
)(SP
.
Языком называют множество последовательностей символов
в каком-либо алфавите. Множества
PSSAA ,,,,
**"*
являются множествами последовательностей символов и,
следовательн, каждое из них можно считать языком. Говорят,
что язык (множество последовательностей действий)
*
SS
реализуется инициальным автоматом, если любая
последовательность действий
)(
*
SPa
, такая, что
Saa )(
***
ведёт из начального состояния
0
b
в какое-либо состояние
i
b
этого автомата и
)()(
**
i
ba
. О входной последовательности
*
a
, которая ведёт в состояние
i
b
, при этом также говорят,
что она реализуется в данном автомате. Классический вопрос,
давно решенный в теории автоматов, - какие языки можно
реализовать в автоматах? (Напомним, что речь пока идёт об
инициальных детерминированных конечных автоматах.) Ответ на
вопрос состоит в следующем. Если множество
*
SS
удовлетворяет условиям полноты, непротиворечивости и
регулярности, то можно построить автомат, реализующий
множество
S
(язык
S
). Сформулируем условия полноты,
непротиворечивости и регулярности для множества
S
.
Условия полноты. Для всякой последовательности
Sa
*
всякое её начало также принадлежит
S
.
Условия непротиворечивости. Не существует ни одной пары
последовательностей
k
aa
11
*
,
Saa
k
22
*
, таких, что
**
21
aa
и
)()(
****
21
aa
.
Условия регулярности. Любая последовательность
Sa
*
может быть получена из пустой последовательности
e
только
в результате последовательного приписывания справа
(конкатенации) конечных или бесконечных циклических
последовательностей в алфавите
A
.
Сокращение числа состояний. Итак полагаем, что исходным
для построения автомата является язык
"*"*
CASS
.
Нашей задачей является построение автомата, который
реализует этот язык. Введём на множестве
eAA
**"
отношение
R
, которое определяется
следующим образом.
Отношение
R
.
**
21
Raa
, если
*"**
, Aaa
21
и
)()(
******
aaaa
21
для всех
*
a
, таких, что
**
aa
1
,
*"**
Aaa
2
.
Нетрудно показать, что отношение
R
является отношением
эквивалентности и разбивает множество
*"
A
на классы
эквивалентности
121
k
QQQ ,,,
, где
1
Q
класс эквивалентности
отношения
R
. которому принадлежит пустая
последовательность
e
. То, что
R
является отношением
эквивалентности, объясняется прежде всего полной
определенностью функции
*
за счёт введения значения
этой функции на запрещённых последовательностях множества
*"
A
.
Множестов классов эквивалентсности можно использовать
для построения автомата, реализующего множество
*
S
, на
основании следующих свойств классов эквивалентности
121
k
QQQ ,,,
, которые являются следствием условий полноты,
непротиворечивости и регулярности множества
последовательностей действий
*"
A
.
Свойство однозначной продолжаемости. Для всякого
действия
*
a
и всякого класса эквивалентности
r
Q
,
11 kr
,
существует единственный класс
t
Q
,
11 kt
, такой, что и
tr
QaQ
, где
aQ
r
множество всех входных
последовательностей
aa
*
, таких, что последовательность
r
Qa
*
.
Свойство связности. Для любого класса
t
Q
,
11 kt
,
существует хотя бы одна последовательность действий
121
t
aaaa
*
, такая, что
211
QaQ
,
322
QaQ
,
,
ttt
QaQ
11
.
Свойство недоопределенности. Если множество допустимых
последовательностей
P
не совпадает с множеством выходных
103
последовательностей
*"
A
, т.е.
*"
AP
, то существует
единственный класс эквивалентности
i
Q
,
11 ki
, все
последовательности которого не принадлежат множеству
P
,
т.е.
PQ
i
. Для определенности будем считать, что этот
единственный класс последовательностей есть
1k
Q
. Из этого
свойства также следует, что пересечение класса
1k
Q
с
множеством
P
пусто
)(
PQ
k 1
, а все остальные классы
r
Q
,
kr 1
, включаются в множество
).( PQP
r
Построение автомата
(обозначим его
*
M
), реализующего язык
*
S
, может быть
осуществлено следующим образом. Классы эквивалентности
121
kk
QQQQ ,,,,
отношения
R
объявляются соответственно
состояниями
121
kk
bbbb ,,,,
автомата
*
M
. Если
ji
QaQ
, то
состояние
i
b
переходит
j
b
, т.е. если
ji
QaQ
, то
ji
bbaf
),(
,
где
f
функция переходов. Функция переходов однозначна
вследствие свойства однозначной продолжаемости. Функцией
выходов автомата
*
M
является функция
)()(
**
ab
j
, где
i
Qa
*
. Функция выходов автомата
*
M
однозначна вследствие
условия непротиворечивости. Начальным состоянием автомата
*
M
является состояние
1
b
, соответствующее классу
эквивалентности
1
Q
, который содержит пустую
последовательность
e
. Вследствие свойства связности
автомат
*
M
будет связным. Таким образом, автомат
*
M
имеет
1k
состояние, каждое из которых соответствует классу
1k
Q
, то это означает, что для любой последовательности
1
k
Qa
*
, имеет место
)(
*
a
и этот класс единственный. Автомат
M
, который реализует язык
S
, отличается от автомата
*
M
отсутствием в нём состояния
1
k
b
и соответственно переходов
в него. Множество состояний автомата
M
обозначим
B
, а
автомата
BM
*
.
Пример сокращения числа состояний. Пусть задано
следующее множество
S
простым перечислением
последовательностей
)(
***
aa
,
},,{
321
aaaA
,
},,{)(
**
321
cccCa
;
,,,,{
221111111
caacaacaecS
},,,,,,,
131212211213222231222131
cacaaacaaacaacaacaacacaa
.
Тогда, согласно определению,
},,,,,,,,,,{)(
321211232221223121111
, aaaaaaaaaaaaaaaaaaaaaeSP
.
Множество
S
содержит все начала своих
последовательностей. В множество
SS \
*
входят
последовательности, которые могут быть получены
продолжением последовательностей множества
S
с соблюдением
свойства регулярности. Если последовательность
SSa \
**
, т.е.
Sa
*
, то
)(
**
a
. Очевидно, что множество
)(
*
SP
, где
SSSS \
**
, содержит все собственные начала своих
последовательностей, т.е. удовлетворяет условиям полноты.
104
Оно удовлетворяет также условиям непротиречивости и
регулярности.
Начнём построение классов эквивалентности с проверки
отношения
R
для двух первых последовательностей
e
,
1
a
множества
P
, проверяя последовательно на равенство
значения функции
*
сначала для продолжения длины 0 этих
последовательностей, затем длины 2,3 и т.д., пока либо не
не получим неравенство этих значений, либо пока не станет
очевидным, что на всех последующих продолжениях функции
одинаковы. В первом случае последовательности помещаются в
разные классы, а во втором в один и тот же. Если при
проверке функций
)(
**
1
a
и
)(
**
2
a
окажется, что
i
ca )(
**
1
, а
)(
**
2
a
, то будем считать, что
)(
**
2
a
.
Проверка на продолжениях длины 0:
11
cae )()(
**
.
Проверка на продолжениях длины 1:
1111
caaea )()(
**
,
2212
caaea )()(
**
,
1313
caaea )()(
**
.
Проверка на продолжениях длины 2:
111111
caaaaea )()(
**
,
221121
caaaaea )()(
**
,
131131
caaaaea )()(
**
,
212112
caaaaea )()(
**
,
222122
caaaaea )()(
**
,
132132
caaaaea )()(
**
)()(
**
13113
aaaaea
,
)()(
**
23123
aaaaea
,
)()(
**
33133
aaaaea
.
Проверка на продолжениях длины 3:
)()(
**
1111111
aaaaaaea
,
)()(
**
2111211
aaaaaaea
,
)()(
**
3111311
aaaaaaea
,
)()(
**
1211121
aaaaaaea
,
)()(
**
2211221
aaaaaaea
,
)()(
**
3111311
aaaaaaea
,
)()(
**
1311131
aaaaaaea
,
)()(
**
2311231
aaaaaaea
,
)()(
**
3311331
aaaaaaea
,
21121112
сaaaaaaea )()(
**
,
12121212
сaaaaaaea )()(
**
,
)()(
**
3121312
aaaaaaea
,
)()(
**
1221122
aaaaaaea
,
)()(
**
2221222
aaaaaaea
,
105
)()(
**
3221322
aaaaaaea
,
)()(
**
1321132
aaaaaaea
,
)()(
**
2321232
aaaaaaea
,
)()(
**
3321332
aaaaaaea
,
)()(
**
1131113
aaaaaaea
,
)()(
**
2131213
aaaaaaea
,
)()(
**
3131313
aaaaaaea
,
)()(
**
2231223
aaaaaaea
,
)()(
**
3231323
aaaaaaea
,
)()(
**
1231123
aaaaaaea
,
)()(
**
1331133
aaaaaaea
,
)()(
**
2331233
aaaaaaea
,
)()(
**
3331333
aaaaaaea
,
Проверку для псоледовательностей
e
,
1
a
можно не
продолжать, поскольку по услвоиям задачи множество
P
содержит только последовательности длиной не более трёх, а
следовательно, на всех ещё не просмотренных их продолжениях
*
a
, длина которых будет не более трёх, функция
)(
**
a
.
Значит, последовательности
e
,
1
a
находятся в отношении
R
и
их можно поместить в один класс
1
Q
и продолжить подобным
образом прверку для одной из последовательностей, и
помещенных в класс
1
Q
, и какой-либо последовательсноти из
множества
P
, еще не помещенной в этот класс. После того
как все последовательности, для которых это можно сделать,
будут помещены в класс
1
Q
последовательснотей, перейдем к
получению класса
2
Q
из числа оставшихся непомещенными в
класс
1
Q
последовательностей, используя аналогичную
процедуру прверки отношения
R
. И так до тех пор, пока все
последовательности не будут распределены по классам. В
результате для нашего примера получим следующие классы
эквивалентности:
106
107
Вопросы и упражнения
1.Что такое искусственный интеллект?
2.Какая черта присуща агенту?
3.Что такое среда и какие бывают среды?
4.выберите одну из известных Вам сред. Отнесите её к
одному из типов и определите, какой агентов наиболее
подходит для Вашей среды и почему?
5.Пусть агент является водителем со своими привычками и
не всегда следует правилам дорожного движения. Выберите тип
агента, который наиболее подходит для каждого из следующих
случаев поведения:
а)всегда использовать тормоза при спуске под гору, если
впереди двигается другой автомобиль, а скорость вашего
автомобиля такова, что Вы его нагоняете;
б)никогда не использовать тормоза при спуске, тормозить
только двигателем;
в)каждый раз при спуске под гору смотреть в зеркало
заднего вида и при наличии автомобиля сзади, который
находится в пределах видимости, использовать тормоза, а в
отсутствие - не использовать. Тормозить двигателем, если в
конце спуска видна группа детей, стоящих на обочине.
6.Объясните понятия микровосприятие, микроситуация,
микрореакция, восприятие, реакция агента?
7.Что такое знания агента? Как они могут быть
представлены?
8.Что делает решатель агента?
9.Что такое состояние среды и чем оно отличается от
восприятия?
10.Что такое цель агента? Чем отличается целенаправленный
агент от целевыбирающего?
11.Из каких двух главных частей состоит агент?
12.Используя таблицу истинности, докажите общезначимость
следующего закона логики высказываний
yxyx )(
.
13.Используя таблицу истинности, докажите общезначимость
следующего закона логики высказываний
yxyx )(
.
14.Используя таблицу истинности, докажите общезначимость
следующего закона логики высказываний
)()()( zxyxzyx
.
15.Используя таблицу истинности, докажите общезначимость
следующего закона логики высказываний
)()()( zxyxzyx
.
16.Используя таблицу истинности, докажите общезначимость
следующего закона логики высказываний
yxyx
.
17.Используя таблицу истинности, докажите общезначимость
следующего закона логики высказываний
)()() xyyxyx (
.
18.Используя таблицу истинности, докажите общезначимость
следующего закона логики высказываний
)()() xyyxyx (
.
19.Определите, к какому типу (общезначимых, выполнимых
или невыполнимых) относятся следующие формулы и докажите
это, используя таблицы истинности или соответствующие
формулы Умный
Умный.
20.Определите, к какому типу (общезначимых, выполнимых
или невыполнимых) относятся следующие формулы и докажите
это, используя таблицы истинности или соответствующие
формулы Умный
Дурак.
21.Определите, к какому типу (общезначимых, выполнимых
или невыполнимых) относятся следующие формулы и докажите
это, используя таблицы истинности или соответствующие
формулы (Умный
Дурак)(
Умный
Дурак).
22.Определите, к какому типу (общезначимых, выполнимых
или невыполнимых) относятся следующие формулы и докажите
это, используя таблицы истинности или соответствующие
формулы Умный
Дурак
Дурак.
23.Определите, к какому типу (общезначимых, выполнимых
или невыполнимых) относятся следующие формулы и докажите
это, используя таблицы истинности или соответствующие
формулы Умный
Дурак
Дурак.
24.Определите, к какому типу (общезначимых, выполнимых
или невыполнимых) относятся следующие формулы и докажите
это, используя таблицы истинности или соответствующие
формулы (Умный
Способный)
Дурак
(Умный
Дурак)
(Способный
Дурак).
25.Определите, к какому типу (общезначимых, выполнимых
или невыполнимых) относятся следующие формулы и докажите
это, используя таблицы истинности или соответствующие
формулы (Умный Дурак)
((Умный Способный)
Дурак).
26.Предполагая, что некоторая среда может быть описана с
использованием только четырех логических переменных
,,,, uzyx
определите сколько моделей может иметь среда для следующих
формул:
а)
yx
; б)
zyx
; в)
yx
.
27.Агент играет роль швейцара в отеле. В его обязанности
входит открыть дверь отеля перед клиентом; помочь ему
донести багаж до стойки администратора, если у клиента есть
багаж; открывать двери автомобиля, подъехавшего к отлею,
если он в это время свободен от других обязанностей, т.е.
цель швейцара - обслужить всех клиентов. Сформулируйте
постановку задачи для среды клиента в пространстве
состояний, если начальным состоянием среды является
состояние, в котором одновременно к дверям отеля подошёл
клиент без багажа и подъехал автомобиль.
109
28.Представьте на языке логики предикатов следующее
предложение русского языка: не все студенты любят математику
и физику.
29.Представьте на языке логики предикатов следующее
предложение русского языка: только один студент любит
историю.
30.Представьте на языке логики предикатов следующее
предложение русского языка: только один студент любит как
историю, так и электронику.
31.Представьте на языке логики предикатов следующее
предложение русского языка: отставание по истории легче
устранить, чем отставание по электронике.
32.Представьте на языке логики предикатов следующее
предложение русского языка: любой охотник, не употребляющий
дичь в пищу, вызывает удивление.
33.Представьте на языке логики предикатов следующее
предложение русского языка: известны женщины, которые любят
мужчин, не являющихся охотниками.
34.Представьте на языке логики предикатов следующее
предложение русского языка: живёт в городе охотник, который
знаком со всеми мужчинами-охотниками этого города.
35.Представьте на языке логики предикатов следующее
предложение русского языка: никто не любит охотника, который
убивает дичь ради развлечения.
36.Запишите условное предложение русского языка в виде
правил логики предикатов: если Вы любите детективы, то
сегодня вечером можете посмотреть прекрасный фильм из этой
серии.
37.Запишите условное предложение русского языка в виде
правил логики предикатов: по утрам подают кофе и бутерброды
с ветчиной.
38.Запишите условное предложение русского языка в виде
правил логики предикатов: может быть я заскочу к вам
вечером, если успею.
39.Запишите условное предложение русского языка в виде
правил логики предикатов: я её одновременно люблю и
ненавижу.
40.Запишите условное предложение русского языка в виде
правил логики предикатов: если бы вы вовремя ушли с работы,
вы бы успели к ужину. если бы вы успели к ужину, то
попробовали бы прекрасное мороженое. Если бы вы попробовали
это мороженое, то всегда бы уходили с работы вовремя.
41.Сформулируйте на языке логики предикатов аксиомы,
которые описываю отношения родства между внуками, бабушками,
110