5.3 Индивидуальные задания

Варианты индивидуальных заданий указаны в таблице. Для заданий 1, 4 – 8 указан номер автомата(см. Приложение). Для заданий 2, 3 указаны буквы – пункты задания.

Вариант	Задания
								8.
	№ 1	г), л)	л), д)	№11	№ 2	№ 7,8	№16	№24
	№ 2	б), к)	г), и)	№12	№ 3	№ 8,9	№17	№23
	№ 3	в), и)	е), к)	№13	№ 4	№ 9,10	№18	№22
	№ 4	г), з)	ж),к)	№14	№ 5	№ 1,10	№19	№20
	№ 5	д),ж)	з), ж)	№15	№ 6	№ 1,2	№20	№21
	№ 6	е), л)	и),д)	№11	№ 7	№ 2,3	№21	№19
	№ 7	ж),к)	и),в)	№12	№ 8	№ 3,4	№22	№18
	№ 8	з), ж)	к), з)	№13	№ 9	№ 4,5	№23	№17
	№ 9	и),д)	л),в)	№14	№ 10	№ 5,6	№24	№16
	№ 1	и),в)	б),к)	№11	№ 2	№ 7,8	№16	№23
	№ 2	б),ж)	г), и)	№12	№ 3	№ 8,10	№17	№22
	№ 3	л), д)	е), к)	№11	№ 4	№ 9,10	№18	№21
	№ 4	г), и)	ж),к)	№14	№ 5	№ 1,9	№19	№20
	№ 5	е), к)	з), ж)	№11	№ 6	№ 1,3	№20	№19
	№ 6	ж),к)	и),д)	№15	№ 7	№ 2,5	№21	№18
	№ 7	з), ж)	и),в)	№12	№ 8	№ 3,64	№22	№17
	№ 8	и),д)	г), л)	№13	№ 9	№ 4,7	№23	№16
	№ 9	и),в)	б), к)	№14	№ 10	№ 5,8	№16	№23
	№ 10	к), з)	в), и)	№15	№ 9	№ 6,9	№17	№22
	№ 1	л),в)	г), з)	№11	№ 2	№ 7,10	№16	№20
	№ 2	б),к)	д),ж)	№12	№ 3	№ 5,9	№17	№21
	№ 3	г), и)	е), л)	№13	№ 4	№ 4,10	№18	№22
	№ 4	е), к)	ж),к)	№14	№ 5	№ 3,10	№19	№19
	№ 5	ж),к)	з), ж)	№15	№ 6	№ 1,7	№20	№16
	№ 6	з), ж)	и),д)	№11	№ 7	№ 2,8	№21	№17
	№ 7	и),д)	и),в)	№12	№ 8	№ 3,9	№22	№21
	№ 8	и),в)	г), к)	№13	№ 9	№ 4,10	№23	№20
	№ 9	к), з)	б), и)	№14	№ 10	№ 2,6	№18	№24

1. Для заданного автомата найдите:

а) самую короткую цепочку, допускаемую автоматом;

б) три другие цепочки, допускаемых этим автоматом;

в) три цепочки, которые отвергаются этим автоматом.

2. Постройте конечный автомат со входным алфавитом {0, 1}, который допускает в точности следующее множество цепочек:

а) Все входные цепочки.

б) Ни одной входной цепочки.

в) Входную цепочку 101.

г) Две входные цепочки: 01, 0100.

д) Все входные цепочки, кончающиеся на 1 и начинающиеся с 0.

е) Все цепочки, не содержащие ни одной единицы.

ж) Все цепочки, содержащие в точности три единицы.

з) Все цепочки, в которых перед и после каждой единицы стоит 0.

и) Пустую цепочку и 011.

к) Все входные цепочки, кроме пустой и цепочки 11.

л) Цепочки, у которых единицы и нули чередуются.

3. Постройте конечные распознаватели для описанных ниже множеств цепочек из нулей и единиц. Затем превратите каждый распознаватель в процессор с концевым маркером. Наконец сделайте так, чтобы процессор обнаруживал допустимость и недопустимость цепочек как можно скорее.

а) Число единиц четное, а число нулей – нечетное.

б) Между вхождениями единиц четное число нулей.

в) Число вхождений пары 00 нечетное, причем допускаются наложения пар друг на друга.

г) Число вхождений пары 00 четное, причем не допускаются наложения пар друг на друга.

д) Каждый третий символ – единица.

е) Имеется, по крайней мере, одна единица

ж) За каждым вхождением пары 11 следует 0.

з) Перед каждым вхождением пары 11 следует 0.

и) За каждым вхождением пары 11 следует 01.

к) За каждым вхождением пары 01 следует 10.

л) После четного числа вхождения единиц следует четное число нулей, после нечетного числа вхождения единиц – нечетное число нулей.

4. Опишите словами множества цепочек, распознаваемых каждым из следующих автоматов.

5. Для каждого из автоматов найдите входную цепочку или цепочки с минимальной суммарной длиной, такие, что под их действием

а) каждое возможное состояние имеет место хотя бы раз,

б) каждый возможный переход происходит хотя бы раз.

6. Найдите различающую цепочку (если она существует) для следующей пары автоматов.

7. Найдите недостижимые состояния автомата

8. Построить минимальный автомат эквивалентный данному автомату.