Теория автоматов в Computer Science 11

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

Граф переходов автомата Мили, соответствующий этой граф-схеме, приведен на рис. 9.б.

Используя этот граф переходов, построим автоматную программу (листинг 1).

Листинг 1

Program Evklid_Automat; {Автоматная реализация алгоритма Евклида}

Var a,b,y:Integer;      {Автомат Мили}

Begin

y:=0;                  {Переменная y обозначает номер состояния}

Repeat

Case y of

0: Begin

ReadLn(a,b);

y:=1;

End;

1: If a>b Then Begin a:=a Mod b; y:=2; End

Else Begin b:=b Mod a; y:=2; End;

2: If (a=0) Or (b=0) Then Begin WriteLn(‘HOD=’,a+b); y:=0; End

Else y:=1;

End;

Until y=0;

End.

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

В теории алгоритмов само понятие «алгоритм» часто определяется с помощью машины Тьюринга. В 1936 году Алан Тьюринг предложил гипотетическое устройство (которое сейчас называется машиной Тьюринга), представляющее собой формальную модель вычислителя и определил алгоритм как программу для этой машины [1]. По сути, машина Тьюринга является результатом добавления к обычному конечному автомату потенциально бесконечной памяти. Оказывается, такое простое расширение обеспечивает существенное изменение возможностей применения машины Тьюринга по сравнению с конечными автоматами.

Похожие записи

• Нет ничего похожего