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

182 { , 111 F Λ → =      ∗→ •→∗ ∗→∗ = Λ 1 1 1 G Затем применить полученный алгоритм к слову : а ) Р =1111111 ; б ) Р = ∗ 1111 ; в ) Р =1 ∗ 111 ; г ) Р = ∗∗ . Результат проверить , последовательно применяя к заданному слову алгоритм F , затем G . 20. Пусть имеем нормальный алгоритм F над алфавитом А , схема которого записана с использованием букв из А и произвольного конечного числа букв , не принадлежащих А . Обозначим эти буквы , не принадлежащие А , через S 1 ,S 2 ,…,S n , т . е . В = А ∪{ S 1 ,S 2 ,…,S n } . Тогда алгоритм F над алфавитом А можно считать заданным в алфавите В . Показать , что для рассматриваемого алгоритма F существует вполне эквивалентный ему в алфавите А нормальный алгоритм , схема которого построена только с использованием букв алфавита С = А ∪{α , β} ( α , β∉ В ) . Можно ли исключить одну из букв α или β , если п > 1 ? 21. Для каждого из приведенных далее алгоритмов над алфавитом А = { а ,b } найти вполне эквивалентный ему нормальный алгоритм , схема которого записана только с использованием букв а , b, α , β : ( )            → → → ∈ → → → → = α Λ γ β β β βγ α α α ε α bb aa Axx x b b a a F 1 ;         → → → → → = α Λ γ γ γ β β α a b b b b a F 2 ;          → •→ → → → → = a b b a F 3 γ δ δ γγ γ αβ β α α . 22. Пусть А – некоторый алфавит . Составьте нормальный алгоритм над А , позволяющий для произвольных слов P и Q в алфавите А выяснять , одинаковы эти слова или нет . ( Указание : рассмотрите слово P ∗ Q ( где ∗∉ А ) и постройте алгоритм , сравнивающий в словах P и Q буквы , стоящие первыми слева и справа от ∗ , затем вторыми от ∗ и т . д .) 23. Пусть А = { 0,1,2,…,9 } . Составьте нормальный алгоритм над А , который любое число п , записанное в десятичной системе счисления , преобразует в п +1 . 24. Будем рассматривать нормальные алгоритмы в алфавите А . До сих пор мы применяли для их задания « схемы » - столбцы формул подстановок . Однако можно задавать каждый нормальный алгоритм в виде одного слова , которое получается следующим образом . Пусть α , β , γ∉ А . Выпишем друг за другом в порядке очередности формулы подстановок алгоритма F заменой стрелки знаком α , точки – знаком β и присоединением после каждой подстановки знака γ . Получаемое так слово будем называть изображением алгоритма F и