Математическая логика и теория алгоритмов

к слову: а) Р=11111; б) Р=*111*1; в) Р=**; г) Р=1*1'!'1. Если «да», то указать результат применения. ' 3. Пусть P=babbbc слово в алфавите А={а,Ь,с},. нормальны горитм В задан схемой В ={аЬ-^а. В какое слово перерабатывает данный алгоритм слово Р? 4. Пусть задан алфавит = с} и нормальный алгоритм в алфа­ вите yi: [b Л В=\ [с -> У1 Применим ли алгоритм В к любому слову в алфавите Если он применим к некоторому слову Р, то в какое слово он его перерабаты­ вает? Ь-^оЛ а->оА с->с 5. Пусть ^={(3,6,с} иВ = Как действует данный алгоритм? Применим ли он к любому слову в алфавите А7 6. Построить нормальный алгоритм, стирающий последнюю бу­ кву каждого непустого слова Р в алфавите А. Является ли построен­ ный алгоритм алгоритмом в алфавите А или над алфавитом А? 7. Пусть - русский алфавит. Построить нормальный алгоритм над алфавитом А> который преобразует слово «муха» в слово «слон», а любое другое слово в алфавите А в пустое слово. При этом, если слово «муха» входит в некоторое слово Q, например 2=черемуха, то слово Q алгоритм должен переработать в пустое слово. 8. Пусть А - русский алфавит. Построить нормальный алгоритм над алфавитом А, который преобразует слово «слон» в слово «муха», а любое другое слово в алфавите А в пустое слово. При этом, если слово «слон» входит в некоторое слово 2 , например <2=заслон, то слово Q алгоритм должен переработать в пустое слово. 266