П эрвы й сим вол остальная часть строки

0 Г~'©^г"""~^'......-Ь

Строка

0 5 ■©•"""'^......Ю

Рис. 4.4. Варианты принятия строки: а) после чтения ее первого символа X; б) после выполнения скрытого перехода

Эти правила можно перевести на язык Prolog следующим образом:

accepts; State, [ ]):- % Принять пустую строку final! State).

Глава 4. Использование структур: примеры программ

accepts! State, [X 1 Rest]):- % Принять после чтения первого символа transt State, X, Statel), acceptst Statel, Rest).

accepts (State, String):- ^:'^:. Принять после выполнения скрытого перехода Silent(State, Statel), accepts! Statel, String).

Этой программе можно, например, задать вопрос о возможности принятия строки aaab, следующим образом:

?- accepts! SI, [a,a,a,b]).

yes

Как уже было показано, программы Prolog часто способны решать более общие проблемы, чем те, для решения которых они первоначально были разработаны. В данном случае можно также задать эмулятору приведенный ниже вопрос о том, в каком первоначальном состоянии должен находиться данный конечный автомат, чтобы он мог принять строку аЬ.

?- accepts! S, [а,Ь]). S = S1;

S = S3

Любопытно отметить, что можно также задать вопрос, каковы все строки с дли­ной 3, которые могут быть приняты в состоянии si.

?- accepts! SI, [X1,X2,X3]}.

XI = а

Х2 = а

ХЗ - Ъ;

XI = Ь

Х2 - а

ХЗ - Ь;

по

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

7- String = [_,_/_), accepts I SI, String). String = [a,a,b]; String = Ib,a,b]; no

С этой программой можно проводить дальнейшие эксперименты, задавая даже еще более общие вопросы, например, о том, из каких состояний автомат принимает входные строки с длиной 7.

Для последующего экспериментирования может потребоваться внесение измене­ний в структуру автомата путем модификации отношений final, trans и silent. Автомат, приведенный на рис. 4.3, не содержит каких-либо циклических скрытых путей (путей, состоящих только из скрытых переходов). А если в автомат на рис. 4.3 будет введен новый переход: silent С S1, S3)

то в нем появится скрытый цикл. Но теперь работа эмулятора может нарушиться, например, при поиске ответа на следующий вопрос:?- accepts! 51, [a)).

Этот вопрос вынудит эмулятор до бесконечности переходить по циклу в состояние si, притом что программа будет постоянно искать какой-то способ перейти в конеч­ное состояние.