Темы кр

Моделирование машины Тьюринга

Стр 320,

Книга 3. Логический подход к ИИ:от классической логики к классическмоу программированию.

Использование формальных языков

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

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

Недетерминированный конечный автомат

Многие задачи решаются представлением их терминов состояний и переходов в их состояниях.

Абстракция такого подхода отражена в идее конечного автомата. Автоматы легко представлять графически.

Пример ниже

Кружки – состояния автомата. Епсилон – переход.

Начальным состоянием явл то, в котрое входит стрелка ниоткуда.

Финальное состояние обозначается двойными кружками.

Переходы между состояниями обозначаются направленными дугами. Около дуги показан входной символ по которому переходит этот автомат.

По символу А из состояния0 можно перейти в 0 а можно и в первое состояние…

Из нулевого состояния по символу А можно перейти либо в первое состояние либо остаться в нулевом. Поэтому автомат недетерминированный.

В этом автомате есть переходы, помеченные символом ε. Он обозначает спонтанный переход. Автомат может сам по себе перейти из нулевого во второе состояние. Он может там побыть и вернуться назад в 0 состояние. Эти ε переходы тоже явл источником недетерминизма. Автомат может вести себя так или иначе. Каждый такой переход это возможность поступить двояка.

Как автомат распознает строки?

Если для данной строки есть путь по дугам, переходам автомата из каждого состояния финальное такое что последовательность меток дуг будет образовывать входную последовательность.

Если взять последовательность

aabab

Она принимается автоматом.

Из нулевого состояния по символу а мы переходим тоже в 0 состояние, по след а в ервое состояние, по b во второе. Далее спонтанно через эпсилон опять в нулевое по а в первое и по символу b во второе, он явл финальным. Эпсилон пустой символ который никак не влияет на последовательность.

Этот автомат можно писать фактами, представленными ниже.

Переход/3 для перехода по входному символу.

ε - переход /2, спонтанны переход.

переход(s₀,a,s₀).

переход(s₀,a,s₁).

переход(s₁,b,s₂).

ε-переход(s₂,s₀).

ε-переход(s₀,s₂).

начальное(s₀).

конечное(s₂).

Рассмотрим процедуру которая проверяет принимается цепочка или нет.

%баз случай, пустая строка допускается из конечного состояния

допускается(S,[]):-

конечное(S).

%общ случ L допуск из состо S если есть ε-переход из S в Sn, из этого сост допуск заданная строка L

допускается(S,L):-

ε-переход(S,Sn),

допускается(Sn,L).

%общ случай

допускается(S,[X|Xs]):-

переход(S,X,Sn),

допускается(Sn,Xs).

В прологе уже заложен недетрминизм…

допускается(X):-

начальное(S), допускается(S,X).

Из какого состояния допускается цепочка «ab»?

?- допускается(S,[a,b]).

S = s₀

Какие цепочки, состоящие из трёх символов, допускаются из состояния s₁?

?- допускается(s₁,[X₁,X₂,X₃]).

X₁ = b

X₂ = a

X₃ = a

Перейдем к синтаксическому анализу на прологе, рассмотрим вопрос использования грамматических правил.

Для того чтобы задать грамматику языка нужно задать алфавит или множество слов языка. Конкретные слова мы будем называть терминалами.

Множество всех терминалов обозначим через сигма ∑

Есть синтаксические категории N, которыми можно определять множество раз, последовательности слов языка.

∑ {человек, несет,…}

N {подлежащее, сказуемое}

Это всё синтаксические категории.

Синтаксические категории определяются продукциями (множество P).

n::= // определяется один нетерминал

n::= v1,v2,vn

n принадл N

Vi принадл N объед сигма

Один нетерминал нужно выбрать в качестве стартового. С него будет начинаться разбор предложения.

Нетерминалы ниже заключены в угловые скобки

<Предложение> ::= <Подлежащее> <Сказуемое>

<Подлежащее> ::= <Существительное>

<Подлежащее> ::= <Прилагательное> <Существительное>

<Сказуемое> ::= <Глагол-неперех.>

<Сказуемое> ::= <Глагол-перех.> <Дополнение>

<Прилагательное> ::= большой

<Прилагательное> ::= маленький

<Существительное> ::= кот

<Существительное> ::= человек

<Глагол-неперех.> ::= ходит

<Глагол-неперех.> ::= стоит

<Глагол-перех.> ::= несёт

<Глагол-перех.> ::= ест

<Дополнение> ::= яблоко

<Дополнение> ::= ведро

Такие деревья нужно строить в процессе синтаксического разбора. Они называются деревьями разбора.

Как этот разбор можно выполнить на прологе? Ниже

предложение(S) :- подлежащее(S1), сказуемое (S2), append(S1,S2,S).

подлежащее(S):- существительное(S).

подлежащее(S):- прилагательное(S1),

существительное(S2). append(S1,S2,S).

прилагательное([большой]).

прилагательное([маленький]).

append – основной предикат, сцепление строк (конкатенация).

Пользуясь предикатом предложение можно проверить явл заданная последовательность слов предложением языка.

Задача синтаксического разбора – основанная выч нагрузка ложится на процедуру append. А эта процедура будет постоянно заново строить новый список.

Для того чтобы списки сцеплять эффективно нужно использовать разностные представления списков.

Разностный список – это пара списков L1 - L2, обозначающая список L.

L = [a,b,c]

L1 = [a,b,c,d,e]

L2 = [d,e]

Варианты представления списка L:

[a,b,c] – []

[a,b,c,d|T] – [d|T]

[a,b,c|T] – T % разностный список, который можно продолжить

Пустой список:

X – X

Посмотрим как работает append для разностных список

appendr(A1-Z1,Z1-Z2,A1-Z2).

L1 = [a,b,c,d,e]

L2 = [d,e]

Чтобы сцепить два списка [a,b,c] и [d,e] нужно представить их в виде [a,b,c|T1] – T1 и [d,e|T2] – T2

и выполнить запрос:

appendr([a,b,c|T1] – T1, [d,e|T2] – T2, L-[]).

T1 = [d,e]

T2 = []

L = [a,b,c,d,e]

Она ничего не делает кроме сопоставления своих параметров.

предложение(S-S0) :- подлежащее(S1-S2), сказуемое (S3-S4), appendr(S1-S2,S3-S4,S-S0).

Равенства будут взяты из append. Эти равенства можно сразу включить в продукцию не пользуясь append.

В прологе есть синтаксическое расширение, пользуясь которым можно продукции грамматики записывать в более удобной форме.

Есть оператор….

Параметры не записывается явно, они подозреваются

Если мы введем такую продукцию, то это соответствует правилу (можно обойтись без структуры)

Если в продукции исп терминал, то термин заключ в квадратные скобки(это список из одного атома).

Для того чтобы описать синтаксис какого либо языка достаточно его перепечатать в таком виде…

В синтаксических правилах можно исп дополнительные аргументы и дополнительные условия подцель.

Эти возможности позв исп атрибутные грамматики или транслирующие… т.е. с помощью грамматики можно построить результат трансляции.

Дополнительные параметры записываются обычным образом перечислением в круглых скобках.

Основные параметры скрыты…

Дополнительные условия заключаются в фигурные скобки. Для того чтобы их не спутать с нетерминалами.