Карпов. СодержаниеПредислови Конечные автоматы
 Скачать 1.07 Mb.
|
|
Лемма 2. Пусть L – язык над алфавитом 9 Если: ( n N)( L: | | n)( u,v,w *: =uvw |uv| n |v| 1): ( i N {0}) uv i w L, то L – НЕавтоматный. Сформулируйте лемму 2 словесно по этому выражению логики предикатов. 1.2.3. Эквивалентны ли формулировки лемм 1.3.1 и.1.3.2, или одна из них является следствием другой? Докажите. 1.2.4. Докажите с помощью леммы о накачке, что язык правильных скобочных выражений не является автоматным. 1.2.5. Докажите, что язык над словарем {a, b}, содержащий все цепочки с одинаковым числом вхождений символов a и b, не автоматный. 1.2.6. Докажите, что язык над словарем {a, b}, содержащий все цепочки, в которых число вхождений символов а больше, чем число вхождений символов b, не автоматный. 1.2.7. Докажите с помощью леммы о накачке, что следующие языки не автоматные: а) {a n 2 | n 0}. б) { a 2n b n | n 1}. в) {ww | w {a, b}*}. г) {w {a, b}* | |w| a =2|w| b }. 1.3. Недетерминированные и детерминированные конечно-автоматные распознаватели 1.3.1. Постройте детерминированный конечный автомат, эквивалентный заданному недетерминированному конечному автомату 1.3.2. Постройте детерминированный конечный автомат с входным алфавитом {a, b, с}, распознающий все цепочки: a) точно с одним вхождением символа b. б) не более чем с тремя вхождениями символа b. в) у которых третья буква от конца b. г) не менее чем с двумя вхождениями символа b. 1.3.3. Постройте детерминированный конечный автомат, распознающий все такие цепочки над словарем {a, b, с}, которые начинаются и заканчиваются одинаковыми символами. Указание. Проще сначала построить недетерминированный КА, обладающий этим свойством. 1.3.4. Постройте детерминированный конечный автомат, распознающий все такие цепочки над словарем {a, b, с}, которые начинаются и заканчиваются различными символами. Указание. Проще сначала построить недетерминированный КА, обладающий этим свойством. 10 1.3.5. Постройте детерминированный конечный автомат, распознающий все такие цепочки из цифр, которые представляют число, делящееся на 25. Указание. Проще сначала построить недетерминированный КА, обладающий этим свойством. 1.3.6. Постройте детерминированный конечный автомат, который допускает над словарем ={a,b}: а) пустой язык. б) язык, содержащий только пустую цепочку. в) язык *\L, где L - некоторый заданный автоматный язык. г) язык L*, где L - некоторый заданный автоматный язык. д) все цепочки, заканчивающиеся кодом ааbba. е) все цепочки, включающие строку аbbab. ж) все цепочки, в которых за каждым символом а непосредственно следует b. з) с не менее чем одним вхождением символа а и точно с двумя вхождениями b. и) с четным числом вхождений символов а и нечетным числом вхождений символов b и не менее чем с одним вхождением символа с. 1.3.7. Постройте детерминированный конечный автомат, распознающий все цепочки над словарем {a, b, c}, включающие не менее двух символов а, точно один символ b и не более двух символов с. 1.3.8. Постройте детерминированный конечный автомат, распознающий все такие цепочки над словарем {a, b, с}, у которых две последние буквы совпадают. 1.3.9. Постройте детерминированный конечный автомат со входным алфавитом ={a, b}, распознающий все цепочки из * за исключением тех из них, которые содержат подцепочку aab. 1.3.10. Пусть L такой язык над словарем {a, b, с}, каждая цепочка которого заканчивается символом, не совпадающим с предыдущими символами этой цепочки. Будет ли L автоматным? Если да, то постройте детерминированный конечный автомат, распознающий L. 1.3.11. Обозначим RemoveOneSymbol(w; a), или сокращенно ROS(w; a), операцию по выбрасыванию из цепочки w каждого вхождения символа a. Например, ROS(abac; a) = bc, ROS(bc; a) = bc. Пусть ROS(L; a) = {ROS(w; a) | w L} для любого языка L. Докажите, утверждение: “Если язык L –автоматный, то автоматным является и язык ROS(L; a)”. 1.3.12. Пусть L - автоматный язык над словарем ={a, b, с}. Будет ли автоматным дополнение этого языка, т.е. язык \L? Если да, то по заданному конечному автомату, распознающему L, постройте конечный автомат, распознающий \L. 1.3.13. Пусть L1 и L2 - автоматные языки над словарем {a, b, с}. Будут ли автоматными: а) L1 L2; б) L1 L2; в) L1\L2. 11 Если да, то по двум заданным конечным автоматам А(L1) и А(L2) постройте конечные автоматы А(L1 L2), А(L1 L2) и А(L1\L2). 1.3.14. Постройте детерминированный конечный автомат, моделирующий алгоритм управления кодовым замком с символами {0, 1} и кнопкой “Открывай”. Автомат должен открывать дверь тогда и только тогда, когда кнопка “Открывай” нажата после любой набранной двоичной последовательности, которая заканчивается кодом 1010010. Заметьте, что кнопки “Сброс” в автомате не нужно: любая цепочка, заканчивающаяся на 1010010, является допустимой (это значит, что набор может происходить с любого состояния автомата). 1.3.15. Арифметические выражения с четырьмя арифметическими операциями {+, -, *, /}записаны без скобок в обычной инфиксной форме, постфиксной форме (польской инверсной записи), и в префиксной форме. Являются ли автоматными соответствующие языки? Если да, то постройте распознающие конечные автоматы. Примеры цепочек для арифметического выражения a+b*с/а-b в постфиксной форме (ПОЛИЗ): “abc*a/+b-”, а в префиксной форме: “-+a/*bcab”. 1.4. Трансляция автоматных языков 1.4.1. Постройте транслятор простейшего языка присваиваний Simple в программу для стековой машины. Правой частью оператора присваивания могут быть либо операнд (целая константа, либо переменная), либо одна бинарная операция над парой операндов. Другими видами оператора являются операторы ввода и вывода значения операнда. Имя переменной задается одной буквой „а‟ с целым индексом: а1, а2, и т.п. Символ * помечает начало и конец программы, символы пробела и перевода строки не учитывать. Пример программы на языке Simple: * а1:=ввод; а2:=-54; а3:=а2*а1; вывод(а3) * 1.4.2. Язык EXPR содержит операции присваивания переменным значений арифметических выражений без скобок c операциями {+, -, *, }, а также операции вывода. Числа только целые. Выражение в операторе присваивания и операторе вывода имеет не более одной арифметической операции. При таких ограничениях язык – автоматный. Постройте транслятор с этого языка на язык стековой машины. Пример программы на языке EXPR: begin у:=3; x:=y 5; 12 y:=7- x; z:=3*y; вывод(x+z). end 1.4.3. Окно для указания номеров печатаемых страниц в программе Word позволяет выдавать эти номера через запятую. В качестве номеров страниц также может использоваться пара А-В, где А и В – натуральные числа, причем А не обязательно больше В (например: 2, 23, 43-32, 3- 5). Пробелы являются разделителями наряду с запятыми. В конце цепочки стоит символ eot . Постройте транслятор языка, выдающий последовательные номера печатаемых страниц в том порядке, в котором указано. 1.4.4. Структура данных, задающая BDD двоичной функции, состоит из перечисления вершин бинарной диаграммы, например: {<5,x1,4,3>; <4,x2,2,0>; <3,x2,0,2>; <2,x3,1,0>}. Для каждой вершины задан ее уникальный номер, имя двоичной переменной, помечающей вершину, а также два номера вершин, с которыми данная вершина связана при значениях переменной 0 и 1. Постройте конечный автомат, распознающий все такие описания. Постройте транслятор из такого описания в программу вычисления значения функции по значениям переменных. 1.4.5. Постройте синтаксические диаграммы и семантические действия на них для трансляции коэффициентов системы линейных уравнений в списочную структуру матрицы значений коэффициентов и вектора значений правых частей. Пример цепочки языка описания системы уравнений: Решить систему 4 уравнений: -3.56 a[1] +15.0 a[4] = 23.64; 0.26 a[2] +25.6 a[3] -3.5 a[4] = 0.0; 13.36 a[2] +28.8 a[4] = -5.34; 5.2a[1]+23.88 a[3] = 234.5 методом Гаусса. 1.4.6*. Постройте транслятор языка представления чисел римской системы счисления. Проверьте работу транслятора на примерах римских чисел: MMIX = 2009, XLIII = 43, XC = 90, CD = 400, CMXCVII = 997. 1.4.7. На основе распознающего конечного автомата постройте программу, которая по последовательности целых, идущих по возрастанию, возвратит строку из набора непрерывных интервалов. Например, после обработки текста “1, 2, 3, 6, 7, 8, 10, 12, 13 eot” должна быть выдана строка “1-3; 6-8; 10; 12-13 eot ”. 1.4.8. Постройте синтаксическую диаграмму и семантические действия преобразования текстовых “смайликов” вида „:-)‟ , „:-(„, „:-))‟, „:-((„ в символы , , , 1.4.9. Постройте транслятор автоматного языка, задающего шахматную позицию - расстановку фигур на шахматной доске. Пример записи позиции: Белые: Крg2, Фd4, Лe3, Cе5, пп. b2, d7, f2, g4, h3 (9). Черные: Крg8, Фd8, Лb7, Kd3, пп. b5, c4, f7, g7, g5 (9). 13 1.4.10. Постройте транслятор автоматного языка, задающего решение шахматного этюда. Пример записи этюда: 1. Крd2 Kb2 2. Kpc2 Kpa5 3. Kpb3 Kpa5 4. Kd6! c4+ 5. K:c4+ Kpb5 ... . Выход транслятора – команды по перемещению фигур. 14 2. Регулярные множества, регулярные выражения и автоматные языки 2.1. Регулярные множества и регулярные выражения 2.1.1. Пусть L 1 ={ac, bcc}, L 2 ={a, c, bc } – два множества цепочек. Постройте множества L 1 L 2 , L 1 3 L 2 , L 1 L 2 2 , L 1 *, L 2 + 2.1.2. Постройте регулярное множество, определяемое регулярным выражением ab*+ba*. 2.1.3. Чему равны множества: а) *; б) + ; в) { }*; г) { } + ; д) {а}*; е) {а} + 2.1.4. Докажите, что ((ab)*)*= (ab)*, построив регулярные множества, задаваемые этими регулярными выражениями. 2.1.5. Определите, принадлежит ли слово 1010 языку, определенному регулярным выражением 10*(10+01)00*. 2.1.6. Постройте регулярное выражение, определяющее следующий язык над алфавитом {0, 1}. Язык содержит слова, в котором каждый ноль, если он вообще есть, с обеих сторон окружен единицами. Примеры слов языка: 11010111101, 10111. 2.2. Регулярные выражения и конечные автоматы 2.2.1. Постройте минимальные детерминированные конечные автоматы с входным алфавитом ={a, b}, распознающие языки, заданные регулярными выражениями: а) a*b*; е) a*a*; б) a*+b*; ж) (a*b*)*; в) (a*+b*)*; з) (a*b*+b)*b; г) ( ba + bab)* и) ab*b*a*b; д) (a+b)a*b*; к) (a+b)*(b*+a*). 2.2.2. По заданному конечному автомату–распознавателю постройте регулярное выражение, задающее тот же язык, который распознает автомат. 15 2.2.3. Язык над алфавитом {a, b, c} задан регулярным выражением a*a (bc)*a. Принадлежат ли этому языку следующие слова: aabcbca, aa, abc, a, aaaa. 2.2.4. Постройте детерминированный конечный автомат, распознающий язык, заданный регулярными выражениями: а) a*(a+b)*a. б) (a*с*a*)*b(c*a*c*)*. в) (a*a*. г) a*b*a*. 2.2.5. Постройте детерминированный конечный автомат с входным алфавитом ={a, b}, распознающий язык * - L, где L – язык, заданный регулярным выражением a*b*a. 2.2.6. Все возможные последовательности событий обращения к ограниченному буферу (запись w и выборка t) представляют собой регулярный язык. Для буфера емкостью 1 этот язык определяется регулярным выражением (wt)*. Постройте регулярные выражения, определяющие все правильные последовательности обращения к буферу емкостью 2 и 3. 2.2.7. Постройте регулярное выражение, описывающее язык L1-L2, если L1 задается регулярным выражением ab*c*, а L2 задается регулярным выражением а*bс. 2.2.8. Постройте детерминированный конечный автомат, распознающий все цепочки словаря {a, b, c} а) заданные регулярным выражением b*(a*ba)*. б) за исключением цепочек языка, заданного регулярным выражением с*(a+b)*c. б) кроме тех, которые задаются регулярным выражением a*(ab*+c*)*. г) которые НЕ содержат ни одной подцепочки языка, задаваемого регулярным выражением ab*с. д) которые содержат в качестве подцепочки какую-либо из цепочек языка, задаваемого регулярным выражением ab*с. е) кроме тех, которые в качестве подцепочек включают слова, заданные регулярным выражением a(b+c*)*. 2.2.9. Постройте регулярное выражение и детерминированный конечный автомат, задающие над алфавитом {0, 1}: а) язык все слова которого начинаются с символа 0 и содержат, по крайней мере, два символа 1. б) язык, все слова которого не содержат двух единиц подряд. 2.2.10. Постройте детерминированный конечный автомат, который распознает пересечение двух таких регулярных языков над словарем {a, b, с}, которые задаются регулярными выражениями R1=a*(b+c)* и R2=a (b*+c*). 2.2.11. Cовпадают ли регулярные языки, заданные регулярными выражениями a*(a*+b)*a и aa*(a+b)*a? 16 2.2.12. Задайте все возможные цепочки десятичных цифр, которые представляют числа, делящиеся на 5: а) недетерминированным конечным автоматом; б) детерминированным конечным автоматом; в) регулярным выражением. 2.2.13. Равны ли два регулярных выражения R1= +(ab+a)(ab+a)* и R2=(a*ab)*a*? 2.2.14. Опишите регулярным выражением язык, являющийся пересечением языков, задаваемых регулярными выражениями R1=a*b* и R2=b*a*. 2.2.15. Заданы два регулярных выражения R1=( +b)b*a* и R2=(bb+b*)(ba*+a*). Совпадают ли регулярные множества L(R1) и L(R2)? 2.2.16. Проверьте, будет ли L(R1) L(R2) для R1 = ( +b*+ab)*a и R2 = a(ab+b*). Каков общий алгоритм определения того, что ли один из регулярных языков является подъязыком другого? 2.2.17. Постройте регулярное выражение, описывающее все цепочки а) внутри которых не встречается цепочка abba. б) внутри которых не встречается цепочка bbaa. Указание. Сначала лучше построить конечный автомат, допускающий все цепочки, внутри которых есть эта подцепочка abba, а потом построить автомат, допускающий дополнение языка, допускаемого первым автоматом, а по этому автомату построить регулярное выражение, описывающее язык, допускаемый автоматом. 2.2.18. Пусть L1 и L2 - два регулярных множества над словарем V. Будут ли регулярны множества: а) V*; б) V*-L1; в) V* - L1*; г) L1-L2; д) L1 L2; е) L1 L2? Обоснуйте свой ответ. 2.2.19. Все возможные последовательности событий обращения к ограниченному буферу (запись, р от put и выборка, t от take) представляют собой язык. Анализ статического кода параллельной программы, работающей с таким буфером, может выявить ошибку, если такая последовательность не принадлежит языку. Постройте регулярные выражения, определяющие все правильные и все неправильные последовательности обращения к буферу емкостью 2. 2.2.20. Все возможные правильные последовательности событий в параллельных программах, составляющие так называемый “response pattern” (шаблон отклика), когда два события S (send) и R (receive) идут друг за другом, описываются регулярным выражением (SS*RR*)*. а) Постройте минимальный конечный автомат, который будет распознавать последовательности событий, соответствующие шаблону отклика. б) Постройте минимальный конечный автомат, который будет распознавать последовательности событий, не соответствующие шаблону отклика. 17 в) Постройте минимальный конечный автомат, который будет распознавать последовательности событий, не соответствующие шаблону (DSS*RR*)*, где D – разделитель сессий. 2.2.21. Какие подстроки на основе регулярного выражения, записанного в расширенном синтаксисе php, будут выбраны в тексте? Регулярное выражение Tекст а) / [^\s]о(т|p|б)+ и?/ “отис, ботрис, обормотрис” б) / [^34][0-9] {3} \w / “324b – 235s- 013” в) / [ щ ц ] (u|e)+ п?/ “соответствующие цепочки ” г) / \w [\w\d]* \+? / “ab231+ 2 = fotka25” 2.2.22. Какое регулярное выражение позволит выбрать из произвольного текста все адреса электронной почты (см.задачу 1.1.11)? 2.2.23. Докажите, что ((ab)*)*= (ab)*, построив минимальные детерминированные конечные автоматы, распознающие соответствующие регулярные зыки. 2.2.24. По регулярному выражению в стандартной записи: (\+|\-| ) [0-9]* [0-9]+([eE](\+| \-|) [0-9]+) постройте несколько примеров цепочек соответствующего регулярного языка. Постройте детерминированный конечный автомат, распознающий такие цепочки. 2.2.25. Для конечного словаря и любого языка L * обозначим tail(L)={w * | u *: uw L }. Иными словами, tail(L) – это множество всех „хвостов‟ цепочек языка L. Постройте детерминированный конечный автомат, допускающий язык tail(L), где L задается регулярным выражением ab*c. 2.2.26. Для конечного словаря и любой цепочки w * обозначим w R – цепочку, обратную цепочке w, например, для w=болван w R =навлоб. Постройте алгоритм, проверяющий, содержит ли регулярный язык L * такую непустую цепочку w, что w R L. Примените этот алгоритм к языку, заданному регулярным выражением a*bcb*. 2.2.27. Постройте КС-грамматику, порождающую тот же язык, который определяется регулярным выражением (a+c+ba+bc)*(b+ ). 2.2.28. Определите языки, которые задаются следующими регулярными выражениями в конкретной нотации: а) (\+?[0-9])+ | (-?[0-9])+ б) (\+?[0-9])+ | ([0-9])+ в) (\+\d)+ | (-?\d)+ |