Теория и реализация языков программирования



         

Регулярные множества и выражения


3.1.1. Показать, что множества, соответствующие двум данным регулярным выражениям, совпадают,

1) (a*b)c и a*(bc); 2) a*b и b + aa*b; 3) b(b + ab)*a и b(b*ab)*b*a; 4) b(ab + b)* и bb*a(bb*a)*:

3.1.2. Заменить каждое из следующих выражений эквивалентным, в котором не используются знак "+":

1) (a + b)*; 2) (a + bb + ba)*; 3) (a + (bb + ab)*)*:

3.1.3. Найти регулярные выражения, обозначающие языки, все слова которых - элементы множества {0, 1}*:

1) оканчивающиеся на 011, 101, 110; 2) начинающиеся с 110, 101 или 011; 3) у которых каждый третий символ есть 0 или каждым второй - 1; 4) не содержащие ни одной из подстрок 011 и 101; 5) содержащие каждую из подстрок 011 и 101; 6) начинающиеся с 011 и оканчивающиеся на 110 или 101; 7) начинающиеся с 011 или 110 и оканчивающиеся на 101; 8) начинающиеся с 011 и содержащие вхождения подстроки 110; 9) {01n|n > 1}; 10) {01n0|n > 0}; 11) {0m1n|n, m > 1}; 12) {

{0, 1}* : |
|=3 - целое неотрицательное число}; 13) {
a|
{0, 1}+, a
{0, 1}, a входит в
}; 14) {(010)n|n > 0}; 15) {0m|m > 2} или {1n|n > 0}; 16) {(01)m(10)n|m
0, n
0}; 17) содержащее четное число символов 0 и нечетное число символов 1; 18) содержащее четное число символов 0 или четное число символов 1.

3.1.4. Является ли язык, состоящий из всех цепочек из 0 и 1, не содержащих подцепочки 010, регулярным?

3.1.5. Является ли язык, состоящий из всех цепочек из 0 и 1, содержащих чeтное число 0 и нечeтное - 1, регулярным?

3.1.6. Является ли язык, состоящий из всех цепочек чeтной длины в алфавите{fa, b, c}, регулярным?

3.1.7. Регулярен ли

а) язык формул вида A*(B), где A, B

{a, b}+? б) язык формул вида (A1.A2), где для i = 1,
Ai есть либо слово в алфавите {a, b}, либо, в свою очередь, формула? в) язык формул вида (A + B), где A, B
{a, b}+? г) язык формул вида (A1)A2, где для i = 1,
Ai есть либо слово в алфавите {a, b}, либо, в свою очередь, формула?

3.1.8. Определить язык, состоящий из всех идентификаторов, с помощью:

а) регулярного выражения; б) леволинейной грамматики; в) конечного автомата; г) праволинейной грамматики.

3.1.9. Будет ли регулярным язык L = {x

{a, b}* : |x|a

четно и |x|b нечетно}?

3.1.10. Построить праволинейную грамматику, порождающую язык L всех слов в алфавите {0, 1}, содержащих чeтное число единиц и нечeтное число нулей. Будет ли она однозначной?

3.1.11. Построить регулярное выражение для языка LR, где L - язык всех слов в алфавите {0, 1}, содержащих чeтное число единиц и нечeтное число нулей.




Содержание  Назад  Вперед