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

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

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

Предположим, даные две задачи:
* Задача 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/1ZyUQf2J25Ndk0qQEueWsrQeJ-Dao0JnMM-tePSVwzXw/edit?usp=sharing). Обратите внимание на комментарии.

Необходимо создать 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}`. Определить, входит ли в слово `P` символ `a`.
Возвращаемый результат: `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 баллов**