Памятью

АВТОМАТЫ И ПРЕОБРАЗОВАТЕЛИ С МАГАЗИННОЙ

Упражнения.

5.1. Покажите, что следующие языки не являются А-языками:

(а) {0 ⁿ 1 0 ⁿ | n ³ 1},

(б) {ww | w Î {0,1} ^* }

(в) L(G), где G определено правилами S ® aSbS ½ c.

5.2. Покажите, что следующие языки не контекстно-свободны:

(а) {a ⁱ b ⁱ c ^j | j £ i};

(б) {a ⁱ b ^j c ^k | i < j < k};

(в) {a ⁱ b ^j a ^j b ⁱ | j £ i};

(г) {a ^m b ⁿ a ^m b ⁿ | m, n ³ 1};

(д) {a ⁱ b ^j c ^k | все числа i, j, k разные}

5.3. Пусть имеется следующая серия непересекающихся языков: L_ми - язык мужских имен - {Миша, Андрей, Петя,... }, L_жи - язык женских имен - {Марина, Таня, Катя,... }, L_си - язык “средних” имен - {Валя, Саша, Женя,... }, L_мф - язык мужских фамилий - {Шамашов, Сидоров, Петров,... }, L_жф - язык женских фамилий - {Наянова, Михеева, Соловьева,... } и язык “средних” фамилий L_сф = {Кричевер, Пономаренко, Перебейнос,... }. Требуется с помощью операций над заданными языками построить язык L - всех правильных сочетаний имен и фамилий. Попробуйте оптимизировать вашу запись.

5.4. С помощью операций над языками постройте язык L - правильных процедур Паскаля, если имеются: язык заголовков, начала и концов процедур L_p, L_begin, L_end; языки описания переменных L_var, L_const, L_type; языки операторов присваивания L_:=; ветвлений - L_if, L_case; циклов L_while, L_for и т.п. При этом считается, что перечисленные языки охватывают всю рассматриваемую конструкцию.

5.5. Пусть имеется язык заголовков цикла - L_while, языки начала и конца блоков L_begin и L_end, язык оператора присваивания L_:=. Постройте язык циклов L, считая, что тело цикла могут составлять операторы присваивания, вложенные или/и чередующиеся циклы данного типа.

5.6. Постройте грамматики объединения, итерации, конкатенации, обращения, подстановки и пересечения языков со следующими правилами грамматики:

G₁: S ® aA ½ bB ½ c G₂: S ® aA

A ® aS ½ a A ® bA ½ bC

B ® b C ® kA ½ cS ½ d

(а) рассматривая исходные языки как КС-языки,

(б) рассматривая их как А-языки.

Введем понятие автомата с магазинной памятью - тип распознавателя, представляющего собой естественную модель синтаксических анализаторов контекстно-свободных языков. Автомат с магазинной памятью - это односторонний недетерминированный распознаватель, в потенциально бесконечной памяти которого элементы информации хранятся и используются так же, как патроны в магазине автоматического оружия, т.е. в каждый момент доступен только верхний элемент магазина. Схема МП-автомата представлена на рис. 6.1.

Дата добавления: 2015-06-27