Приклади на складання програм для МТ

Розглянемо приклади на складання програм для МТ, щоб продемонструвати деякі типові прийоми програмування на МТ.

Для скорочення формулювання задач введемо наступні дві угоди:

- буквою Р позначатимемо вхідне слово;

- буквою А позначатимемо алфавіт вхідного слова, тобто набір тих символів, з яких і тільки яких може полягати Р (відмітимо, проте, що в проміжних і вихідному словах можуть з'являтися і інші символи).

Приклад 1. Дана машина Т'юринга із зовнішнім алфавітом А = {0, 1} (тут 0 - символ порожньоїкомірки)алфавітом внутрішніх станів Q = {q₀, q₁, q₂) і з наступною функціональною схемою (програмою):

q₁0 ->q₂0П; q₂0 ->q₀1; q₁1 ->q₁1П; q₂1 ->q₂1П.

Запишіть складену програму (функціональну схему) побудованої машини Т'юринга у вигляді таблиці.

Подивимося, в яке слово переробить ця машина слово 101, виходячи із стандартного початкового положення. Послідовно виписуватимемо конфігурації машини при переробці нею цього слова. Маємо стандартне початкове положення:

На першому кроці діє команда: q₁1 -> q₁ 1П

В результаті на машині створюється наступна конфігурація:

На другому кроці діє команда: q₁0 -> q₂0П і на машині створюється конфігурація:

Нарешті, третій крок обумовлений командою: q₂0 -> q₀ 1Н. В результаті його створюється конфігурація:

Ця конфігурація є завершальною, тому що машина виявилася в стані зупинки q₀.

Таким чином, початкове слово 101 перероблено машиною в слово 10101.

Приведіть послідовність конфігурацій при переробці цією машиною слова 11011, виходячи з початкового положення, при якому в стані q₁ оглядається крайня ліва комірка, в якій міститься символ цього слова (самостійно проаналізуйте кожен крок роботи машини, вказуючи, яка команда зумовила його):

Таким чином, слово 11011 перероблено машиною в слово 110111.

Приклад 2(переміщення автомата, заміна символів)

А={0,1,2,3,4,5,6,7,8,9}. Нехай Р - непорожнє слово; значить, Р - це послідовність з десяткових цифр, тобто запис ненегативного цілого числа в десятковій системі. Вимагається отримати на стрічці запис числа, яке на 1 більше числа Р.

Рішення.

Для вирішення цієї задачі пропонується виконати наступні дії:

1. Перегнати автомат під останню цифру числа.

2. Якщо це цифра від 0 до 8, то замінити її цифрою на 1 більше і зупинитися; наприклад:

3. Якщо ж це цифра 9, тоді замінити її на 0 і зрушити автомат до попередньої цифри, після чого таким же способом збільшити на 1 цю передостанню цифру; наприклад:

4.Особливий випадок: в Р тільки дев'ятки (наприклад, 99). Тоді автомат зрушуватиметься вліво, замінюючи дев'ятки на нулі, і врешті-решт виявиться під порожньою клітиною. У цю порожню клітину потрібно записати 1 і зупинитися (відповіддю буде 100):

У вигляді програми для МТ ці дії описуються таким чином:

	q₁	q₂
	q₁0П	q₀1
	q₁1П	q₀2
	q₁2П	q₀3
	q₁3П	q₀4
	q₁4П	q₀5
	q₁5П	q₀6
	q₁6П	q₀7
	q₁7П	q₀8
	q₁8П	q₀9
	q₁9П	q₂0Л
Λ	q₂ΛЛ	q₀1

Пояснення.

q₁- цей стан, в якому автомат "біжить" під останню цифру числа. Для цього він увесь час рухається управо, не міняючи видимі цифри і залишаючись в тому ж стані. Але тут є одна особливість: коли автомат знаходиться підостанньою цифрою, то він ще не знає про це (адже він не бачить, що записано в сусідніх клітинах) і визначить це лише тоді, коли потрапить на порожню клітину. Тому, дійшовши до першої порожньої клітини, автомат повертається назад під останню цифру і переходить в стан q₂ (управо рухатися вже не потрібно).

q₂ - цей стан, в якому автомат додає 1 до тієї цифри, яку бачить в даний момент. Спочатку це остання цифра числа; якщо вона - в діапазоні від 0 до 8, то автомат замінює її цифрою, яка на 1 більше, і зупиняється. Але якщо це цифра 9, то автомат замінює її на 0 і зрушується вліво, залишаючись в стані q₂. Тим самим, він тепер додаватиме 1 до попередньої цифри. Якщо і ця цифра дорівнює 9, то автомат замінює її на 0 і зрушується вліво, залишаючись в колишньому стані q₂, оскільки повинен виконати ту ж саму дію - збільшити на 1 видиму цифру. Якщо ж автомат зрушився вліво, а у видимій клітині немає цифри (а "порожньо"), то він записує сюди 1 і зупиняється.

Відмітимо, що для порожнього вхідного слова наша задача не визначена, тому на цьому слові МТ може поводитися як завгодно. У нашій програмі, наприклад, при порожньому вхідному слові МТ зупиняється і видає відповідь 1.

Перевірити роботу на словах: 890, 49387.

Приклад 3(аналіз символів)

А={ а, b, c }. Перенести перший символ непорожнього слова Р в його кінець. Наприклад:

Рішення.

Для вирішення цієї задачі пропонується виконати наступні дії:

1. Запам'ятати перший символ слова Р, а потім стерти цей символ.

2. Перегнати автомат управо під першу порожню клітину за Р і записати в неї символ, який запам'ятали.

Як "бігати" управо, ми вже знаємо з попереднього прикладу. А ось як запам'ятати перший символ? Адже в МТ немає іншого пристрою, що запам'ятовує, окрім стрічки, а запам'ятовувати символ в якійсь клітині на стрічці безглуздо: як тільки автомат зрушиться вліво або вправо від цієї клітини, він тут же забуде цей символ. Що робити?

Вихід тут такий - потрібно використовувати різні стани автомата. Якщо перший символ - це а, те потрібно перейти в стан q₂, в якому автомат біжить управо і записує у кінці а. Якщо ж першим був символ b, тоді потрібно перейти в стан де робиться все те ж саме, тільки у кінці записувати символ b. Якщо ж першим був символ с, тоді переходимо в стан q₄, в якому автомат дописує за вхідним словом символ _с. Отже, то, яким був перший символ, ми фіксуємо переводом автомата в різні стани. Це типовий прийом при програмуванні на МТ.

З урахуванням сказаного програма буде такою:

	q₁	q₂	q₃	q₄
а	q₂ΛП	q₂ a П	q₃ a П	q₄ a П
b	q₃ΛП	q₂ b П	q₃ b П	q₄ b П
с	q₄ΛП	q₂ с П	q₃ с П	q₄ с П
Λ	q₁ΛП	q₀ a	q₀ b	q₀ с

Розглянемо поведінку цієї програми на вхідних словах, що містять не більше одиного символу. При порожньому слові, яке є "поганим" для задачі, програма зациклиться - автомат, знаходячись в стані q₁ і потрапляючи увесь час на порожні клітини, нескінченно переміщатиметься управо. (Звичайно, в цьому випадку програму можна було б зупинити, але ми спеціально зробили зациклення, щоб продемонструвати таку можливість.)

Якщо ж у вхідному слові рівно один символ, тоді автомат зітре цей символ, зрушиться на одну клітину управо і запише в неї цей символ:

q₀

Таким чином, слово з одного символу просто зрушиться на клітину управо. Це допустимо. Адже клітини стрічки не нумеровані, тому місце розташування слова на стрічці ніяк не фіксується і переміщення слова вліво або управо помітити не можна. У зв'язку з цим не вимагається, щоб вихідне слово обов'язково знаходилося в тому ж місці, де було вхідне слово, результат може виявитися і лівіше, і правіше за це місце.

Приклад 4(порівняння символів, стирання слова)

А={а, b, c}. Якщо перший і останній символи (непорожнього) слова Р однакові, тоді це слово не міняти, а інакше замінити його на порожнє слово.

Рішення.

Для вирішення цієї задачі пропонується виконати наступні дії:

1. Запам'ятати перший символ вхідного слова, не стираючи його.

2. Перемістити автомат під останній символ і порівняти його з тим, що запам'ятався. Якщо вони рівні, то більше ні чого не робити.

3. Інакше знищити усе вхідне слово.

Як запам'ятовувати символ і як переганяти автомат під останній символ слова, ми вже знаємо з попередніх прикладів. Стирання ж вхідного слова реалізуєтьсязаміною усіх його символів на символ Λ. При цьому, раз вже автомат виявився у кінці слова, переміщатимемо автомат справа наліво до першої порожньої клітини.

Ці дії описуються наступною програмою для МТ (нагадаємо, що хрестик в елементі таблиці означає неможливість появи відповідної конфігурації при виконанні програми):

	q₁	q₂	q₃	q₄	q₅	q₆	q₇	q₈
a	q₂ a	q₂ aП	q₀ a	q₄ aП	q₈ a	q₆ aП	q₈ a	q₈ΛЛ
b	q₄ b	q₂ bП	q₈ b	q₄ bП	q₀ b	q₆ bП	q₈ b	q₈ΛЛ
c	q₆ c	q₂ cП	q₈ c	q₄ cП	q₈ c	q₆ cП	q₀ c	q₈ΛЛ
Λ	q₀Λ	q₃ΛЛ	х	q₅ΛЛ	х	q₇ΛЛ	х	q₀Λ

Перевірити роботу на словах: aabcbc, cbbaa.

Приклад 5(видалення символу із слова)

А={ а, b }. Видалити із слова Р його другий символ, якщо такий є.

Рішення.

Здавалося б, це завдання вирішити просто: потрібно зрушити автомат під клітину з другим символом і потім очистити цю клітину:

Проте нагадаємо, що усередині вихідного слова не повинно бути порожніх клітин. Тому після видалення другого символу потрібно "стискувати" слово, перенісши перший символ на одну клітину управо. Для цього автомат повинен повернутися до першого символу, запам'ятати його і стерти, а потім, знову зрушившись управо, записати його в клітину, де був другий символ. Проте початковий "похід" управо до другого символу, щоб його стерти, і наступне повернення до першого символу є зайвими діями: яка різниця - переносити перший символ в порожню клітину або в клітину з якимсь символом? Тому відразу запам'ятовуємо перший символ, стираємо його і записуємо замість другого символу:

У вигляді програми для МТ усе це записується так:

	q₁	q₂	q₃
а	q₂ΛП	q₀ а	q₀ b
b	q₃ΛП	q₀ а	q₀ b
Λ	q₀Λ	q₀ а	q₀ b

Перевірити роботу на словах:aabbba, ababab.

Індивідуальні завдання

Записати МТ у вигляді програми, та навести перевірку роботи програми на двох словах.

№ варіанта	завдання
1,5.	А={ а, b, c }. Приписати ліворуч до слова Р символ b (Р → b Р).
2,6.	А={ а, b, c }. Приписати справа до слова Р символи bс (Р → Р bс).
3,7.	А={ а, b, c }. Замінити на а кожен другий символ в слові Р.
4,8.	А={ а, b, c }. Залишити в слові Р тільки перший символ (порожнє слово не міняти).
9, 15.	А={ а, b, c }. Залишити в слові Р тільки другий символ (порожнє слово не міняти).
10, 16.	А={ а, b, c }. Залишити в слові Р тільки останній символ (порожнє слово не міняти).
11, 17.	А={ а, b, c }. Приписати ліворуч до слова Р символ a (Р → a Р).
12, 18.	А={ а, b, c }. Замінити на b кожен другий символ в слові Р.
13, 19.	А={ а, b, c }. Залишити в слові Р тільки перший символ (порожнє слово не міняти).
14, 20.	А={ а, b, c }. Приписати справа до слова Р символи ас (Р → Р ас).
21, 25.	А={ а, b, c }. Залишити в слові Р тільки останній символ (порожнє слово не міняти).
22, 26.	А={ а, b, c }. Приписати ліворуч до слова Р символ с (Р → с Р).
23, 27.	А={ а, b, c }. Приписати справа до слова Р символи аb (Р → Р аb).
24, 28.	А={ а, b, c }. Замінити на с кожен другий символ в слові Р.
29.	А={ а, b, c }. Залишити в слові Р тільки перший символ (порожнє слово не міняти).
30.	А={ а, b, c }. Залишити в слові Р тільки останній символ (порожнє слово не міняти).
31.	А={ а, b, c }. Залишити в слові Р тільки другий символ (порожнє слово не міняти).

ЛАБОРАТОРНА РОБОТА №2

Машини Т'юринга

Приклад 6(стискування слова)

А={а, b, c}. Видалити із слова Р перше входження символу а, якщо такий є.

Рішення.

У попередньому прикладі ми переносили на позицію управо тільки один символ. У цьому ж прикладі ми в циклі переноситимемо управо усі початкові символи b і c вхідного слова - до першого символу а або до порожньої клітини:

Центральний момент тут - як перенести символ х з лівої клітини в чергову клітину, де знаходиться деякий символ у, щоб потім цей символ у можна було перенести в праву клітину? Якщо через q_х позначити стан, в якому у видиму клітину потрібно записати символ х, що знаходився раніше в клітині ліворуч, тоді цю дію можна зображувати так:

Для цього пропонується виконати такт q_у x П, в якому об'єднані слідуючі три дії: по-перше, у видиму клітину записується символ х, узятий з клітини ліворуч; по-друге, автомат зрушується управо - під клітину, в яку потім потрібно буде записати тільки що замінений символ у; по-третє, автомат переходить в стан q_у в якому він і виконуватиме цей запис.

Повторення таких тактів в циклі і приведе до зрушення управо на одну позицію початкових символів вхідного слова. Цей цикл повинен закінчитися, коли в черговій клітині опиниться символ а або Λ (у= а або у=Λ), а на початку циклу можна вважати, що на місце першого символу ліворуч переноситься"порожній" символ (х=Λ). У результаті виходить наступна програма для МТ:

	q₁	q₂	q₃
a	q₀ΛП	q₂ b П	q₀ с
b	q₂ΛП	q₂ b П	q₂ с П
c	q₃ΛП	q₃ b П	q₃ с П
Λ	q₀Λ	q₀ b	q₀ с

У цій програмі слід звернути увагу на такт q₀ΛП, який виконується в конфігурації < а, q₁>, тобто коли першим символом вхідного слова є а. Ясно, що потрібно просто стерти цей символ і зупинитися. Проте в цьому такті вказано ще і зрушення управо. Навіщо? Нагадаємо, що у момент останову автомат повинен знаходитися під вихідним словом (під будь-яким його символом), тому ми і зрушуємо автомат з порожньої клітини на клітину з першим символом вихідного слова, який у вхідному слові був другим.

Перевірити роботу на словах: abbcaa, cbccbaa

Приклад 7(вставка символу в слово)

А={ а, b, c }. Якщо Р - непорожнє слово, то за його першим символом вставити символ а.

Рішення.

Ясно, що між першим і другим символами слова Р потрібно звільнити клітину для нового символу а. Для цього потрібно перенести на одну позицію влівоперший символ (на старому місці його можна не видаляти), а потім, повернувшись на старе місце, записати символ а:

Перенесення символу на одну позицію вліво аналогічне перенесенню символу управо, про що говорилося в двох попередніх прикладах, тому приведемо програму для МТ без додаткових коментарів. Відмітимо лише, що в станахq₂, q₃іq₄ автомат може бачити тільки порожню клітину, а в станіq₅ він обов'язково бачить перший символ вхідного слова, але не порожню клітину.

	q₁	q₂	q₃	q₄	q₅
a	q₂ a Л	х	х	х	q₀ a
b	q₃ b Л	х	х	х	q₀ a
c	q₄ c Л	х	х	х	q₀ a
Λ	q₀ Λ	q₅ a П	q₅ b П	q₅ c П	х

Перевірити роботу на словах: abbcc, caabbc

Приклад 8(розсунення слова)

А={ а, b, c }. Вставити в слово Р символ а за першим входженням символу c, якщо такий є.

Рішення.

Переглядаємо вхідне слово зліва направо до порожньої клітини або до першого символу с. В першому випадку с не входить в Р, тому нічого не робимо. У другому випадку потрібно звільнити місце для символу а, що вставляється, для чого зрушуємо початок слова Р (від першого символу до знайденого символу с) на одну позицію вліво. При цьому здійснюємо таке зрушення справа наліво - від символу с на початок слова, раз вже автомат знаходиться під цим символом. Крім того, щоб потім не повертатися до позиції, що звільнилася, починаємо це зрушення із запису а замість знайденого символу с. Оскільки це циклічне зрушення вліво реалізується аналогічно циклічному зрушенню управо з прикладу 5, то не пояснюватимемо його, а відразу приведемо програму для МТ:

	q₁	q₂	q₃	q₄
а	q₁ а П	q₂ а Л	q₂ b Л	q₂ c Л
b	q₁ b П	q₃ а Л	q₃ b Л	q₃ c Л
c	q₄ а Л	q₄ а Л	q₄ b Л	q₄ c Л
Λ	q₀ Λ Л	q₀ а	q₀ b	q₀ c

Перевірити роботу на словах: bbcbbc, abcabc

Приклад 9(формування слова на новому місці)

А={ а, b, c }. Видалити з Р усі входження символу а.

Рішення.

Попередні приклади показують, що в МТ досить складно реалізуются вставки символів в слова і видалення символів із слів. Тому іноді простіше не розсовувати або стискувати вхідне слово, а формувати вихідне слово в іншому, вільному місці стрічки. Саме так ми і поступимо при рішенні цієї задачі.

Конкретно пропонується виконати наступні дії:

1. Вихідне слово будуватимемо праворуч від вхідного. Щоб розмежувати ці слова, відокремимо їх деяким допоміжним символом, наприклад знаком =, відмінним від усіх символів алфавіту А (див. крок 1). (Нагадаємо, що на стрічці можуть бути записані не лише символи з алфавіту вхідного слова.)

2. Після цього повертаємося на початок вхідного слова (див. крок 2).

3. Тепер наше завдання - перенести в циклі усі символи вхідного слова, окрім а, управо за знак = у формоване вихідне слово.

Для цього аналізуємо перший символ вхідного слова. Якщо це а, тоді стираємо його і переходимо до наступного символу (див. крок 3). Якщо ж перший символ - це b або c, тоді стираємо його і "біжимо" управо до першої порожньої клітини (див. крок 4), куди і записуємо цей символ (див. крок 5).

Знову повертаємося наліво до того символу, який став першим у вхідному слові, і повторюємо ті ж самі дії, але вже по відношенню до цього символу (див. кроки 6-9).

4. Цей цикл завершується, коли при поверненні наліво ми побачимо як перший символ знак =. Це ознака того, що ми повністю проглянули вхідне слово і перенесли усі його символи, відмінні від а, у формоване справа вихідне слово. Потрібно цей знак стерти, зрушитися управо під вихідне слово і зупинитися (див. крок 10).

З урахуванням усього сказаного і будуємо програму для МТ. При цьому відмітимо, що окрім символів а, b і c в процесі рішення задачі на стрічці з'являється знак =, тому в таблиці має бути передбачений стовпець і для цього знаку.

	q₁	q₂	q₃	q₄	q₅
a	q₁ a П	q₂ a Л	q₃ΛП	q₄ a П	q₅ a П
b	q₁ b П	q₂ b Л	q₄ΛП	q₄ b П	q₅ b П
c	q₁ c П	q₂ c Л	q₅ΛП	q₄ c П	q₅ c П
=	x	q₂ = Л	q₀ΛП	q₄ = П	q₅ = П
Λ	q₂=	q₃ΛП	x	q₂ b	q₂ c

Перевірити роботу на словах: aacabac, bbbaccc

Приклад 10(фіксація місця на стрічці)

А={ а, b }. Подвоїти слово Р, поставивши між ним і його копією знак =. Наприклад:

Рішення.

Це завдання вирішується аналогічно попередній: в кінець вхідного слова записуємо знак =, потім повертаємося на початок слова і в циклі усі його символи (у тому числі і а) копіюємо в порожні клітини справа:

Проте є і відмінність: копійовані символи вхідного слова не видаляються, і це призводить до наступної проблеми. Записавши справа копію чергового символу, ми потім повинні повернутися до вхідного слова в позицію цього символу і потім зрушитися управо до наступного символу, щоб скопіювати вже його. Але як дізнатися, в яку позицію вхідного слова потрібно повернутися? Наприклад, звідки ми знаємо в нашому прикладі, що після копіювання першого символу а ми повинні повернутися саме до першого символу вхідного слова, а не до другого або третього? У попередній задачі ми завжди поверталися до першого з символів вхідного слова, що залишилися, а тепер ми зберігаємо усі символи, тому незрозуміло, які символи ми вже скопіювали, а які ще ні. Відмітимо також, що в МТ комірки стрічки ніяк не нумеруються, немає в МТ і лічильників, які дозволили б визначити, скільки символів ми вже скопіювали.

У загальному вигляді проблема, з якою ми зіткнулися, наступна: як зафіксувати на стрічці деяку позицію, в якій ми вже були і до якої пізніше повинні повернутися? Зазвичай ця проблема вирішується так. Коли ми опиняємося в цій позиції вперше, то замінюємо символ, що знаходиться в ній, на його двійник - на новий допоміжний символ, причому різні символи замінюємо на різні двійники, наприклад а на А і b на В. Після цього ми виконуємо якісь дії в інших місцях стрічки. Щоб потім повернутися до нашої позиції, потрібно просто відшукати на стрічці ту клітину, де знаходиться символ А або В. Потім в цій клітині можна відновити колишній символ, якщо нам більше не потрібно фіксувати цю позицію (саме для відновлення колишнього символу і потрібно було замінювати різні символи на різні двійники).

Скористаємося цим прийомом в нашій задачі, виконуючи наступні дії:

1. Як вже сказано, спочатку записуємо знак = за вхідним словом (див. крок 1 вище).

2. Потім повертаємося під перший символ вхідного слова (див. крок 2 вище).

3. Далі замінюємо видимий символ а на двійник А (див. крок 3 нижче), "біжимо" управо до першої вільної клітини і записуємо в неї символ а (див. крок 4). Після цього повертаємося вліво до клітини з двійником А (див. крок 5), відновлюємо колишній символ а і зрушуємося управо до наступного символу (див. крок 6).

Тепер аналогічним чином копіюємо другий символ (замінюємо його на А, в кінець дописуємо а і так далі) і усі наступні символи вхідного слова.

4. Коли ми скопіюємо останній символ вхідного слова і повернемося до його двійника (після кроку 12), то потім після зрушення на одну позицію управо ми потрапимо на знак = (крок 13). Це сигнал про те, що вхідне слово повністю скопійоване, тому роботу МТ потрібно завершувати.

З урахуванням усього сказаного отримуємо наступну програму для МТ:

	q₁	q₂	q₃	q₄	q₅	q₆
a	П	q₂ aЛ	q₄АП	q₄ aП	q₅ aП	q₆ aЛ
b	q₂ bП	q₂ bЛ	q₅ВП	q₄ bП	q₅ bП	q₆ bЛ
=	Х	X	q₀=	q₄ =П	q₅ =П	q₆ =Л
А	Х	X	Х	X	X	q₃ aП
В	Х	X	Х	X	X	q₃ bП
Λ	q₂=Л	q₃=П	х	q₆ a	q₆ b	х

Відмітимо, що в цій програмі можна позбавитися від стану якщо об'єднати його із станом передбачивши в повернення вліво як до порожньої клітини, так і до символів А і В:

Перевірити роботу на словах: bbaba, aabbaa

Індивідуальні завдання

Записати МТ у вигляді програми, та навести перевірку роботи програми на двох словах.

№ варіанта	завдання
1.	А={ а, b, c }. Визначити, чи входить в слово Р символ а. Відповідь: слово з одного символу а (так, входить) або порожнє слово (ні).
2.	А={ а, b, c }. Визначити, чи являється Р словом ab. Відповідь (вихідне слово): слово ab, якщо являється, або порожнє слово інакше.
3.	А={ а, b, c }. Якщо в слово Р не входить символ а, то замінити в Р усі символи b на с, інакше як відповідь видати слово з одного символу а.
4.	А={ а, b, 0,1}. Визначити, чи являється слово Р ідентифікатором (непорожнім словом, що починається з букви). Відповідь: слово а (так) або порожнє слово (ні).
5.	А={ а, b, 0,1}. Визначити, чи являється слово Р записом числа в двійковій системі числення (непорожнім словом, що складається тільки з цифр 0 і 1). Відповідь: слово 1 (так) або слово 0.
6.	А={0,1}. Вважаючи непорожнє слово Р записом двійкового числа, видалити з нього незначущі нулі, якщо такі є.
7.	А={0,1}. Для непорожнього слова Р визначити, чи являється воно записом міри двійки (1, 2, 4, 8,..) в двійковій системі числення. Відповідь: слово 1 (являється) або слово 0.
8.	А={0,1,2,3}. Вважаючи непорожнє слово Р записом числа в четверічній системі числення, визначити, являється воно парним числом або ні. Відповідь: 1 (так) або 0.
9.	А={0,1}. Вважаючи непорожнє слово Р записом числа в двійковій системі, получити двійкове число, рівне збільшеному учетверо числу Р (наприклад: 101 → 10100).
10.	А={0,1}. Вважаючи непорожнє слово Р записом числа в двійковій системі, отримати двійкове число, рівне неповній частці від ділення числа Р на 2 (наприклад: 1011 →101).
11.	А={ а, b, c }. Якщо Р - слово парної довжини (0, 2, 4,..), то видати відповідь а, інакше - порожнє слово.
12.	А={0,1,2}. Вважаючи непорожнє слово Р записом числа в трійковій системі числення, визначити, являється воно парним числом або ні. Відповідь: 1 (так) або 0. (Зауваження: в парному трійковому числі має бути парна кількість цифр 1.)
13.	А={ а, b, c }. Нехай Р має непарну довжину. Залишити в Р тільки середній символ.
14.	А={ а, b, c }. Якщо слово Р має парну довжину, то залишити в ньому тільки ліву половину.
15.	A={ a, b }. Для непорожнього слова P визначити, чи входить в нього ще раз його перший символ. Відповідь: a (так) або порожнє слово.
16.	A={a, b}. У непорожньому слові P поміняти місцями його перший і останній символи.
17.	A={a, b}. Визначити, являється P симетричним словом або ні. Відповідь: a (так) або порожнє слово.
18.	A={a, b}. Подвоїти слово P (наприклад: abb→abbabb).
19.	A={a, b}. Подвоїти кожен символ слова P (наприклад: bab→bbaabb).
20.	A={a, b}. Перевернути слово P (наприклад: abb→bba).
21.	A={0,1}. Вважаючи непорожнє слово P записом двійкового числа, отримати це ж число, але в чотирирічній системі. (Зауваження: врахувати, що в двійковому числі може бути непарна кількість цифр)
22.	A={0,1,2,3}. Вважаючи непорожнє слово P записом числа в чотирирічній системі числення, отримати запис цього числа в двійковій системі.
23.	A={0,1,2}. Вважаючи непорожнє слово P записом позитивного числа в трійковій системі числення, зменшити це число на 1.
24.	A={0,1,2}. Вважаючи непорожнє слово P записом числа в трійковій системі числення, отримати запис цього числа в одиничній системі.
25.	А={ а, b }. Якщо в Р символів а більше, ніж символів b, то видати відповідь а, якщо символів а меншеніж символів b, то видати відповідь b, а інакше як відповідь видати порожнє слово.
26.	А={ а, b, 0,1}. Визначити, чи являється слово Р ідентифікатором (непорожнім словом, що починається з букви). Відповідь: слово а (так) або порожнє слово (ні).
27.	А={ а, b, c }. Нехай Р має непарну довжину. Залишити в Р тільки середній символ.
28.	А={0,1,2}. Вважаючи непорожнє слово Р записом числа в трійковій системі числення, визначити, являється воно парним числом або ні. Відповідь: 1 (так) або 0. (Зауваження: в парному трійковому числі має бути парна кількість цифр 1.)
29.	A={0,1,2}. Вважаючи непорожнє слово P записом позитивного числа в трійковій системі числення, зменшити це число на 1.
30.	А={ а, b, c }. Визначити, чи являється Р словом ab. Відповідь (вихідне слово): слово ab, якщо являється, або порожнє слово інакше.