Разветвление

Этот способ сочетания нормальных алгорифмов задан так:

1) к исходному слову применить алгорифм ;

2) если слово существует и равно пустому слову, то к слову применить алгорифм ;

3) если слово существует и не равно пустому слову, то к слову применить алгорифм и считать слово общим результатом;

4) если слово не определено, то не определен и общий результат.

Теорема о «программировании» разветвления нормальных алгорифмов в виде схемы некоторого нормального алгорифма называется теоремой о разветвлении и формулируется следующим образом.

Теорема (о разветвлении нормальных алгорифмов). Каковы бы ни были нормальные алгорифмы и в алфавитах соответственно, может быть построен алгорифм над объединением алфавитов такой, что для любого слова выполняется следуюшее: 1) если то ; 2) если , то при и при .

Доказательство теоремы о разветвлении основано на предыдущих теоремах: композиции и объединения.

Нормальный алгорифм , который может быть построен согласно теореме о разветвлении, будем обозначать и называть - разветвлением алгорифмов и . Коротко этот алгорифм можно задать такой записью:

.

В программистских терминах -разветвеление можно описать так:

if then else .

Дата добавления: 2015-07-15