# 3. Algorithms, Computability, Turing Machine and Finite-state Machine Home Work

## Які завдання виконувати
Оберить будь-які чотире завдання із списку завдань. Оцінюватися будуть лише ці чотире завдання. Бали за завдання ранжовані по складності.

## Алфавіт
Для кожного завдання алфавіт `Λ` обмежує тільки вхідне слово, результат та процес виконання програми можуть використовувати символи, що не входять до `Λ`.

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

Припустим, є два завдання:
* Завдання 1
Нехай `Λ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ∅}`; `P` — не порожнє слово.Потрібно отримати на стрічці запис числа, яке на `1` більше за `P`.
* Завдання 2
Нехай `Λ = {a, b, c, ∅}`; `P` — не порожнє слово. Якщо перший та останній символи`Р` однакові, тоді це слово не змінювати, а інакше замінити його на порожнє слово.

Формат відповіді має відповідати шаблону, описаному [тут](https://docs.google.com/spreadsheets/d/1fAAtKhgaBSWcP74Cjv2R04ywINoEQAmtgebCUIle0c0/edit#gid=0).

Необхідно створити Google Spreadsheets, додати посилання на цей документ як рішення в Google Classroom, переконатися, що маю право на перегляд документа.

## Завдання

### Завдання 1
`Λ = {a, b, c}`. Приписати ліворуч к слову `P` символ `b` (т.е. `P → bP`).
**1 бал**

### Завдання 2
`Λ = {a, b, c}`. Приписать праворуч к слову `P` символы `bc` (т.е. `P → Pbc`).
**1 бал**

### Завдання 3
`Λ = {a, b, c}`. Зʼясувати, чи входить символ `a` до складу `P` .
Повертаємий результат: `1` — якщо входить, `0` — якщо не входить.
**2 бала**

### Завдання 4
`Λ = {a, b, c}`. Замінити на `a` кожний другий символ в слові `P`.
**2 бала**

### Задача 5
`Λ = {a, b, 0, 1}`. Зʼясувати, чи є слово P записом числа в двійковій системі числення (не порожнім словом, що складається тільки із цифр `0` и `1`).
Повертаємий результат: `1` — якщо так, `0` — якщо ні.
**2 бала**

### Завдання 6
`Λ = {0, 1}`. Для не порожнього слова P зʼясувати, чи є воно записом ступеня двійки (`1, 2, 4, 8, ...`) в двійковій системі числення.
Повертаємий результат: `1` — якщо так, `0` — якщо ні.
Передбачається, що слова с незначними нулями, наприклад `000101`, на вхід не подаються.
**2 бала**

### Завдання 7
`Λ = {0, 1}`. Описати машину Т'юрінга, яка розпізнає парну кількість одиниць.
Повертаємий результат: `1` — якщо парна кількість одиниць, `0` — якщо непарна.
Конфігурація машини Тюрінга є стандартною.
**2 бала**

### Завдання 8
`Λ = {a, b}`. Подвоїти слово `P` (наприклад: `abb → abbabb`).
**4 бала**

### Завдання 9
`Λ = {a, b}`. Перевернути слово `P` (наприклад: `abb → bba`).
**4 бала**

### Завдання 10
`Λ = {a, b}`. Подвоїти кожен символ слова `P` (наприклад: `bab → bbaabb`).
**6 балів**

### Завдання 11
`Λ = {(, )}`. Зʼясувати, чи є слово P сбалансованим по дужках.
Повертаємий результат:`1` — якщо так, `0` — якщо ні.
**8 балів**

### Завдання 12
`Λ = {a, b}`. Якщо в `P` символів `a` більше за символів `b`, тоді повернути `a` як результат; якщо символів `a` меньше за символів `b`, тоді повернути `b`; інакше повернути порожнє слово.
**8 балів**