Сборник задач по теории автоматов (стр. 2 )

Строк длиной может быть .

Строк длиной может быть .

. . .

Строк длиной может быть .

Все эти строки различны, так как имеют разную длину.

Тогда .

Задача 3

Задан алфавит и строка над этим алфавитом. Перечислить префиксы, суф­фиксы и подстроки строки . Оценить, сколькими способами для строки дли­ной можно выбрать суффикс, префикс и подстроку.

a)  ,;

b)  , .

Задача 4

Пусть задан алфавит . Определить перечислением язык :

a)  симметричных строк с длиной , ;

b)  состоящий из строк с равным числом знаков и длиной , , .

Подсчитать число строк языка при произвольном .

Задача 5

Заданы 2 языка и над алфавитами и соответственно. Определить язык , , . Оценить число строк для полученных языков , если известны мощности языков и .

a)  ,;

b)  ,.

Занятие 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.  Приведём несколько примеров строк, принадлежащих заданному языку