Упражнения к третьей главе

3.1. Постройте детерминированные А-грамматики для следующих цепочек, завершающихся символом “;”:

(a) целых чисел без знака и без значащих нулей;

(б) четных целых чисел без знака;

(в) идентификаторов, содержащих четное количество символов;

(г) для цепочек из упражнения 1.5.

3.2. Постройте конечный автомат, который будет распознавать слова go to , причем между ними может быть произвольное число пробелов, включая нулевое.

3.3. Постройте конечные распознаватели для описанных ниже множеств цепочек из нулей и единиц:

(а) число единиц четное, а нулей - нечетное;

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

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

(г) каждый третий символ - единица;

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

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

(а) все входные цепочки;

(б) все входные цепочки, кроме пустой;

(в) ни одной входной цепочки;

(г) входную цепочку 101;

(д) две входные цепочки: 01 и 0100;

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

(ж) все цепочки, не содержащие ни одной единицы;

(з) все цепочки, содержащие в точности три единицы;

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

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

3.6. Постройте детерминированную А-грамматику по следующей недетерминированной:

S ® aAïaBïbBïbD

A ® aBïaSïbD

B ® cSïcBïbDïb

D ® dDïdBïbBïbAïaïc

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

3.8. Найдите детерминированный автомат, эквивалентный следующему недетерминированному: