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, притом что программа будет постоянно искать какой-то способ перейти в конечное состояние.
