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



         

Алгебраические свойства регулярных множеств. Лемма о разрастании.


3.5.1. Будут ли регулярными следующие языки в алфавите {a}:

а) L1 = {{a2n+5}

{a7n+4}, n = 0, 1, ...};

б) L2 = {{a2n+5}

{a7n+4}, n = 0, 1, ...};

в) L3 = {{a4n+5}, n = 0, 1, ..., n

5(mod11)};

д)

L_4 = \{a^{n^2}, n = 0, 1, \ldots \}
.

3.5.2. Будут ли регулярными следующие языки в алфавите ? = {a, b}:

а) язык L1 из всех слов ?*, содержащих подслова a?b; б) язык L2 из всех слов ?*, не содержащих двух b подряд; в) язык L3 из всех слов ?*, не принадлежащих L1 или L2; г) L4 = {{a2n+5b7n+4}, n = 0, 1, ...}?

3.5.3. Задается ли язык {anbm|n

m
1} регулярным выражением?

3.5.4. Является ли грамматика с правилами:

S

aA|bB|C; B
bB|b|?; A
aA|a|?; C
cSC:

праволинейной грамматикой?




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