Занятие 1.1. Формальные языки
Задача 1
Задан алфавит и строка над этим алфавитом. Перечислить префиксы, суф¬фиксы и подстроки строки . Оценить, сколькими способами для строки дли¬ной можно выбрать суффикс, префикс и подстроку.
Решение
1. Множество префиксов .
Множество суффиксов .
Множество подстрок .
2. Подсчитаем число префиксов произвольной строки .
Префиксов длиной может быть .
Префиксов длиной может быть .
. . .
Префиксов длиной может быть .
Префиксов длиной может быть .
Тогда .
3. Аналогично находим ( ).
4. Оценим число подстрок произвольной строки .

Тогда .
Фиксируем -й знак строки в качестве начального знака подстроки и получаем подстрок.
Фиксируем -й знак строки в качестве начального знака подстроки и получаем подстрок.
. . .
Фиксируем -й знак строки в качестве начального знака подстроки и получаем подстроку.
Тогда
Получаем:
Задача 2
Пусть задан алфавит . Определить перечислением язык с длиной строк . Подсчитать число строк языка при произвольном .
Решение
1. .
2. Подсчитаем число строк языка при , где – натуральное число .
Строк длиной может быть .

Строк длиной может быть .
Все эти строки различны, так как имеют разную длину.
Тогда .
Задача 3
Задан алфавит и строка над этим алфавитом. Перечислить префиксы, суф¬фиксы и подстроки строки . Оценить, сколькими способами для строки дли¬ной можно выбрать суффикс, префикс и подстроку.

Задача 4
Пусть задан алфавит . Определить перечислением язык :
a) симметричных строк с длиной , ;
b) состоящий из строк с равным числом знаков и длиной , , .
Подсчитать число строк языка при произвольном .
Задача 5
Заданы 2 языка и над алфавитами и соответственно. Определить язык , , . Оценить число строк для полученных языков , если известны мощности языков и .

Занятие 1.2. Формальные системы
Задача 6
Задана формальная система:
1) Алфавит ;
2) Формулы ;
3) Аксиомы , , есть формулы, тогда , , , – тоже формулы;
4) Правила вывода
Породить произвольную формулу в этой системе и выполнить возможные её тождественные преобразования, используя формальный подход.
Решение
Порождаем произвольную строку, используя пункты 2 и 3.

Задача 7
Задать формальную систему универсального множества над алфавитом .
Решение
1. Зададим алфавит .
2. Формулы .
3. Аксиомы. Пусть и — строки из универсального множества , тогда и — тоже строки из универсального множества .
4. Правила вывода: .
Задача 8
Задать формальную систему:
a) конечных бинарных деревьев;
b) чисел Фибоначчи (последовательность чисел заданная следующим рекуррентным выражением: , где );
Рекомендация: использовать унитарное представление натуральных чисел.
c) арифметики целых чисел над элементарными формулами , , .
Занятие 1.3. Формальные грамматики
Задача 9
Задана формальная грамматика , где , , .
Какой язык она порождает?
Решение
1. Используя множество продукций , породим несколько строк искомого языка.

2. Очевидно, что грамматика порождает язык , где ,
Задача 10
Определить грамматику, которая порождает язык, состоящий из строк алфавита таких, что в каждой из них непосредственно справа от знака стоит знак .
Решение
1. Приведём несколько примеров строк, принадлежащих заданному языку
2. Задаём понятия (нетерминальные знаки), через которые можно выразить свойства строк языка:
— строка заданного языка,
— правильная строка с одним знаком .
3. Сформулируем гипотезу, которая выражает свойства языка через заданные понятия:
Правильная строка языка есть последовательность знаков .
4. Представим гипотезу в виде продукций грамматики , где . Тогда
5. Проверим полученную грамматику на предмет порождения ею строк заданного языка

Для доказательства того, что полученная грамматика порождает заданный язык необходимо использовать метод математической индукции, например, по длине вывода. Ход доказательства зависит от конкретного вида продукций.
Проведём индукцию по длине вывода путём использования первой группы продукций грамматики. При длине вывода 1 и 2 получаем строки, принадлежащие заданному языку. Пусть получена строка языка при длине вывода : , , . И пусть строка может быть преобразована в правильную строку, тогда при длине вывода получим:

Если часть строки удовлетворяет свойствам языка, то и вся строка удовлетворяет свойствам языка.
Вывод: грамматика порождает заданный язык.
Задача 11
Задана формальная грамматика , где

Какой язык она порождает?
Задача 12
Определить грамматики, которые порождают следующие языки:
a) язык, состоящий из строк алфавита таких, что число знаков в строке меньше, чем число знаков ;
b) язык чисел в представлении с фиксированной точкой в десятичной системе счисления;
c) язык целых чисел со знаком и без знака;
d) язык, состоящий из строк алфавита таких, что число знаков в строке равно числу знаков .
Занятие 1.4. Контекстно-свободные грамматики
Задача 13
Контекстно-свободная грамматика (КС-грамматика) задана множеством продукций

Получить эквивалентную ей КС-грамматику без -продукций.
Решение
1. Грамматика является КС-грамматикой, так как все её продукции имеют вид . Грамматика содержит -продукцию, например, .
2. Применим процедуру эквивалентного преобразования грамматики в форму без -продукций:
a) Пусть , , где . Тогда , .
b) Фиксируем -порождающую продукцию
c) Добавляем в продукции из , в которых опущены -порождающие нетерминальные знаки : .
d) Удаляем из зафиксированную продукцию и переносим из в новые -продукции, которые появились в на шаге c: , , .
e) Повторяем шаги b, c, d пока :

f) Так как , то завершаем процедуру.
3. Строим грамматику следующим образом: и содержат те терминальные и нетерминальные знаки, которые присутствуют в продукциях . Далее , а

Задача 14
КС-грамматика задана множеством продукций

Получить эквивалентную ей КС-грамматику без цепных продукций.
Решение
1. Грамматика является КС-грамматикой, так как все её продукции имеют вид . Непосредственно видно, что грамматика содержит цепные продукции.
2. Применим процедуру удаления цепных продукций.
a) Пусть , , где — множество цепных продукций. Тогда . Пусть .
b) Строим вспомогательные множества : , , , .
c) Фиксируем в множестве продукцию вида , например, зафиксируем продукцию .
d) Добавляем в множество всевозможные продукции вида , т.е. .
e) Если все продукции из просмотрены, то завершаем процедуру, иначе повторяем шаги c и d:

f) Так как все продукции из просмотрены, то завершаем процедуру.
3. Строим грамматику следующим образом: и содержат те терминальные и нетерминальные знаки, которые присутствуют в продукциях . Далее , а
Задача 15
КС-грамматика задана множеством продукций

Получить эквивалентную ей КС-грамматику , не содержащую бесполезных нетерминальных знаков.
Решение
1. Грамматика является КС-грамматикой, так как все её продукции имеют вид .
2. Строим множество достижимых знаков .
a) Задаём начальное приближение множества достижимых знаков , куда включаем аксиому достижимую по определению грамматики и те нетерминальные знаки, которые содержаться в правых частях продукций .
b) Строим следующее приближение множества достижимых знаков , где — множество всех нетерминальных знаков из правых частей продукций вида . Тогда получаем .
c) Повторяем шаг b до тех пор, пока приближение множества достижимых знаков на текущей итерации не сравнится с приближением множества достижимых знаков на предыдущей итерации, либо пока приближение множества достижимых знаков на текущей итерации не будет содержать все нетерминальные знаки, т.е. все знаки множества .
d) Так как , то .
3. Строим множество производящих знаков .
a) Задаём начальное приближение множества производящих знаков , куда включаем те нетерминальные знаки, которые непосредственно порождают терминальные строки.
b) Строим следующее приближение множества производящих знаков , где — множество тех нетерминальных знаков, которые непосредственно порождают строки состоящие из терминальных знаков и знаков множества . Тогда получаем .
c) Повторяем шаг b до тех пор, пока приближение множества производящих знаков на текущей итерации не сравнится с приближением множества производящих знаков на предыдущей итерации, либо пока приближение множества производящих знаков на текущей итерации не будет содержать все нетерминальные знаки, т.е. все знаки множества :

d) Так как , то .
4. Строим приведённую грамматику .
a) Определим множество существенных знаков .
b) В включаем те продукции из , которые не содержат бесполезных знаков . Тогда

c) В множество включаем те терминальные знаки из , которые встречаются в продукциях . Тогда .
Задача 16
КС-грамматика задана множеством продукций

Получить эквивалентную ей КС-грамматику без -продукций.
Задача 17
КС-грамматика задана множеством продукций

Получить эквивалентную ей КС-грамматику без цепных продукций.

Занятие 1.5. Разрешимость языков
Задача 18
Грамматика задана множеством продукций

Определить принадлежит ли строка языку .
Решение
1. Грамматика является КС-грамматикой, так как все её продукции имеют вид . Строка является строкой в терминальном алфавите, так как .
2. Зададим вектор , где , , , . Строим систему уравнений относительно множеств вектора следующим образом: если в множестве есть продукции , то запишем уравнение . Тогда получим систему:

3. Решаем систему уравнений .
a) Задаём начальное приближение .
b) Задаём следующее приближение . Тогда получим систему

c) Удаляем из множеств те строки, которые не могут быть подстрокой искомой строки.
d) Повторяем шаги b и c до тех пор, пока искомая строка не появится в множестве или пока система множеств на текущей итерации не совпадёт с системой множеств на предыдущей итерации:

e) Так как искомая строка появилась в множестве , то завершаем процедуру и делаем вывод, что строка принадлежит языку .
Задача 19
Грамматика задана множеством продукций

Определить является ли язык пустым.
Решение
1. Грамматика является КС-грамматикой, так как все её продукции имеют вид .
2. Строим множество производящих знаков .
a) Задаём начальное приближение множества производящих знаков , куда включаем те нетерминальные знаки, которые непосредственно порождают терминальные строки.
b) Строим следующее приближение множества производящих знаков , где — множество тех нетерминальных знаков, которые непосредственно порождают строки состоящие из терминальных знаков и знаков множества . Тогда получаем .
c) Повторяем шаг b до тех пор, пока приближение множества производящих знаков на текущей итерации не сравнится с приближением множества производящих знаков на предыдущей итерации, либо пока приближение множества производящих знаков на текущей итерации не будет содержать все нетерминальные знаки, т.е. все знаки множества .
d) Так как , то .
3. Так как , то .
Задача 20
Грамматика задана множеством продукций:
a) ;
b) .
Определить является ли язык бесконечным.
Решение для пункта а
1. Грамматика является КС-грамматикой, так как все её продукции имеют вид .
2. Найдём множество существенных нетерминальных знаков.
A. Найдём множество достижимых знаков. Так как в первой продукции множества содержатся все нетерминальные знаки множества , то есть множество достижимых знаков.
B. Найдём множество производящих знаков .
a) Задаём начальное приближение множества производящих знаков , куда включаем те нетерминальные знаки, которые непосредственно порождают терминальные строки.
b) Строим следующее приближение множества производящих знаков , где — множество тех нетерминальных знаков, которые непосредственно порождают строки состоящие из терминальных знаков и знаков множества . Тогда получаем .
c) Повторяем шаг b до тех пор, пока приближение множества производящих знаков на текущей итерации не сравнится с приближением множества производящих знаков на предыдущей итерации, либо пока приближение множества производящих знаков на текущей итерации не будет содержать все нетерминальные знаки, т.е. все знаки множества .
d) Так как , то .
C. Таким образом, получили, что все нетерминальные знаки грамматики существенны.
3. Строим такой вывод в грамматике из существенного нетерминального знака , что и , где и состоят из существенных и терминальных знаков: .
4. Так как и существенные знаки, то фрагмент может породить счётное множество строк, т.е. язык бесконечен.
Решение для пункта b
1. Грамматика является КС-грамматикой, так как все её продукции имеют вид .
2. Найдём множество существенных нетерминальных знаков.
A. Найдём множество достижимых знаков. Так как в первой продукции множества содержатся все нетерминальные знаки множества , то есть множество достижимых знаков.
B. Найдём множество производящих знаков .
a) Задаём начальное приближение множества производящих знаков , куда включаем те нетерминальные знаки, которые непосредственно порождают терминальные строки.
b) Строим следующее приближение множества производящих знаков , где — множество тех нетерминальных знаков, которые непосредственно порождают строки состоящие из терминальных знаков и знаков множества . Тогда получаем .
c) Повторяем шаг b до тех пор, пока приближение множества производящих знаков на текущей итерации не сравнится с приближением множества производящих знаков на предыдущей итерации, либо пока приближение множества производящих знаков на текущей итерации не будет содержать все нетерминальные знаки, т.е. все знаки множества .
d) Так как , то .
C. Таким образом, получили, что все нетерминальные знаки грамматики существенны.
3. Строим такой вывод в грамматике из существенного нетерминального знака , что и , где и состоят из существенных и терминальных знаков:

4. Так как не смогли получить вывод в грамматике , описанный в пункте 3, то язык конечен.
Задача 21
Грамматика задана множеством продукций

Найти все строки языка такие, что .
Задача 22
КС-грамматика задана множеством продукций

Найти все строки языка , содержащие 3 знака .