задачи по КС-языкам и магазинным автоматам
Описание файла
PDF-файл из архива "задачи по КС-языкам и магазинным автоматам", который расположен в категории "". Всё это находится в предмете "формальные языки и автоматы" из 6 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст из PDF
Задание 1Регулярные языки и конечные автоматыЗадача 1. Дано регулярное выражение R = a(a|b)∗ a(bb|a).1. Построить по РВ R НКА B.2. По НКА B построить ДКА A1 .3. По РВ R построить ДКА A2 .4. По ДКА A1 или A2 построить минимальный автомат A3 .5. По любому из построенных ДКА Ai построить ДКА для языка L(Ai ).6. По любому из построенных ДКА Ai построить ДКА для языка L(Ai )R .7.
По любому из построенных автоматов построить ПГ G.8. По любому из построенных выше автоматов построить РВ R0 .9. Построить ДКА, распознающий язык L(R) ∩ L(R)R .Задача 2. Дана грамматикаG = ({A, B}, {a, b}, {A → baA|aB; B → bA|a}, A).Построить по грамматике G автомат A.Задача 3. Являются ли регулярными следующие языки:1. L1 = {a2013n+5 | n = 0, 1, . . .} ∩ {a509k+29 | k = 401, 402, . .
.} ⊆ {a}∗22. L = {an | n > 1} ⊆ {a}∗3. L = {w | w = wR } ⊆ {a, b}∗4. L = {w | |w|ab = |w|ba } ⊆ {a, b}∗1.