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

* 7 7 ^ 7 В = < ^ 1 ^ Л^1 V к слову: а) Р=111; Р=**-, ъ) Р=11*] т) Р=*1*11 Если «да», то указать результат применения. 2. Применим ли нормальный алгоритм B = \l^.ll Л^'^Л V к слову: а) Р=11111; б) Р=*111*1; в) Р=**; г) Р=1*1*11 Если «да», то указать результат применения. 3. Пусть P=babbbc слово в алфавите А= {а,Ь,с}, нормальный алгоритм В задан схемой В ={аЬ—>а В какое слово перерабатывает данный алгоритм слово Р1 4. Пусть задан алфавит А={Ь,с} ж нормальный алгоритм в алфавите А: В \Ь ^ Л Применим ли алгоритм В к любому слову в алфавите А1 Если он [с ^ Л применим к некоторому слову Р, то в какое слово он его перерабатывает? b •Л а ^ •Л Как действует данный алгоритм? с ^ с Применим ли он к любому слову в алфавите А1 6. Построить нормальный алгоритм, стирающий последнюю букву каждого непустого слова Р в алфавите А. Является ли построенный алгоритм алгоритмом в алфавите А или над алфавитом А1 7. Пусть А - русский алфавит. Построить нормальный алгоритм над алфавитом А, который преобразует слово «муха» в слово «слон», а любое другое слово в алфавите А в пустое слово. При этом, если слово «муха» входит в некоторое слово Q, например 2=черемуха, то слово Q алгоритм должен переработать в пустое слово. 8. Пусть А - русский алфавит. Построить нормальный алгоритм над алфавитом А, который преобразует слово «слон» в слово «муха», а любое другое слово в алфавите А в пустое слово. При этом, если слово «слон» входит в некоторое слово Q, например 2=заслон, то слово Q алгоритм должен переработать в пустое слово. 9. Пусть заданы алфавит ^4 и некоторое непустое слово Q в этом алфавите. Описать действие нормальных алгоритмов, задаваемых следующими схемами: 179 5. Пусть А= {а,Ь,с} и В