Тема 1.2

Вправа 1. Нехай задано алфавіт D та алфавіт E.

Необхідно:

1) задати мову L₁ в алфавіті D та мову L₂ в алфавіті D довільним способом (крім мов Ø та {ε});

2) виконати операції композиції, конкатенації над мовами L₁ та L₂ та операцію ітерації над результатом виконання операції композиції.

Варіанти задання алфавітів:

1) D = {a₁, a₂, a₃}, E = {1,2,3}; 2) D = {b₁, b₂, b₃, b₄}, E = {0,1};

3) D = {c₁, c₂, c₃}, E = {p₁, p₂, p₃, p₄}; 4) D = {f₁, f₂, f₃}, E = {r₁, r₂, r₃};

5) D = {g₁, g₂}, E ={s₁, s₂, s₃, s₄}; 6) D = {h₁,h₂, h₃}, E = {0,1,2,3};

7) D = {8, 9}, E = {t₁, t₂, t₃, t₄}; 8) D = {i₁, i₂, i₃}, E = {4,5,6,7}.

Розв’язок:

D = {f₁,f₂,f₃}, E = {r₁, r₂, r₃}

Мова L₁ - в алфавіті D: L₁ = {ε, f₁f₂ , f₁f₂f₃, f₁f₃ }.

Мова L₂ - в алфавіті E: L₂ = {r₁r₂, r₂r₃, r₂r₂ }.

Результати виконання операцій:

• композиції L₁ та L₂:

L₁  L₂ = { ε, f₁f₂ , f₁f₂f₃, f₁f₃, r₁r₂, r₂ r₃, r₂ r₂ };

• конкатенації L₁ та L₂:

L₁ L₂ = { r₁r₂, r₂r₃, r₂r₂ , f₁f₂r₁r₂, f₁f₂r₂r₃, f₁f₂r₂r₂ , f₁f₂f₃r₁r₂, f₁f₂f₃r₂r₃, f₁f₂f₃r₂r₂ , f₁f₃r₁r₂, f₁f₃r₂r₃, f₁f₃r₂r₂ };

• ітерації:

{L₁  L₂ }⁰ = {};

{L₁  L₂}¹ = {ε, f₁f₂ , f₁f₂f₃, f₁f₃, r₁r₂, r₂r₃, r₂r₂ };

{L₁  L₂}² = {L₁  L₂} {L₁  L₂}¹ = { ε, f₁f₂ , f₁f₂f₃, f₁f₃, r₁r₂, r₂r₃, r₂r₂ , f₁f₂f₁f₂ , f₁f₂f₁f₂f₃, f₁f₂f₁f₃, f₁f₂r₁r₂, f₁f₂r₂r₃, f₁f₂r₂r₂ , f₁f₂f₃f₁f₂ , f₁f₂f₃f₁f₂f₃, f₁f₂f₃f₁f₃, f₁f₂f₃r₁r₂, f₁f₂f₃r₂r₃, f₁f₂f₃r₂r₂ , f₁f₃f₁f₂ , f₁f₃f₁f₂f₃, f₁f₃f₁f₃, f₁f₃r₁r₂, f₁f₃r₂r₃, f₁f₃r₂r₂ , r₁r₂f₁f₂ , r₁r₂f₁f₂f₃, r₁r₂f₁f₃, r₁r₂r₁r₂, r₁r₂r₂r₃, r₁r₂r₂r₂ , r₂ r₃f₁f₂ , r₂ r₃f₁f₂f₃, r₂ r₃f₁f₃, r₂ r₃r₁r₂, r₂ r₃r₂r₃, r₂ r₃r₂r₂ , r₂r₂ f₁f₂ , r₂r₂ f₁f₂f₃, r₂r₂ f₁f₃, r₂r₂ r₁r₂, r₂r₂ r₂r₃, r₂r₂ r₂r₂ }

і т.д.

{L₁  L₂}ⁿ = { ε, f₁f₂ , f₁f₂f₃, f₁f₃, r₁r₂, r₂r₃, r₂r₂, …}.

Вправа 2. Для слова а₁ а₂ а₃ а₄ вказати всі префікси, суфікси та підслова.

Розв’язок:

Префікси: ε, а₁, а₁ а_{2 ,} а₁ а₂ а_{3 ,} а₁ а₂ а₃ а₄

Суфікси: а_{4 ,} а₃ а_{4 ,} а₂ а₃ а_{4 ,} а₁ а₂ а₃ а_{4 ,} ε

Підслова : ε, а_1, а_2, а_3, а_4, а₁ а_2, а₃ а_{4 ,} а₂ а_{3 ,} а₁ а₂ а_{3 ,} а₂ а₃ а_{4 ,} а₁ а₂ а₃ а₄

Вправа 14. В алфавіті {А, Б, В} визначені мови:

1) L₁= {, AA, AAA, AAAA, …};

2) L₂ ={, AБ, AББ, AБББ, …};

3) L₃ ={, ВА, ВБ, АВ, АВАВ, АВАВАВ, …};

4) L₄ ={АА, АБ, ВА, БА, ВАА, БАА, ВААА, БААА, …};

5) L₅ ={, АБ, ААББ, АААБББ};

6) L ₆ ={А, АА, ААБ, ААВ, ААА};

7) L ₇={А, АБВ, АБВ, АБВ, АБВАБВАБВ, …};

8) L₈={, АБ, АВ, БАВ, БАВАВ, БАВАВАВ,…,Б, ББ, БББ,… };

9) L ₉={АБ…В, АБ…ВАБ…В, АБ…ВАБ…ВАБ…В,… };

10) L₁₀= {, А, Б, В, АА, АБ, АВ, БА, ББ, БВ, ВА, ВБ, ВВ, ААА, ААБ, ААВ, АБА, АББ, АБВ, АВА, АВБ, АВВ, БАА, БАБ, БАВ, ББА, БББ, ББВ, БВА, БВБ, БВВ, ВАА, ВАБ, ВАВ,ВБА, ВББ, ВБВ, ВВА, ВВБ, ВВВ,… };

11) L ₁₁= {АБ, АВ, АБАБ, АБАВ, АВАБ, АВАВ, АБАБАБ, АБАБАВ, АБАВАБ, АБАВАВ,

АВАБАБ, АВАБАВ, АВАВАБ, АВАВАВ,… };

12) L ₁₂ = {АА, АБ, ААА, АБАБ, АААААА, АБАБАБ, …};

13) L ₁₃ = {АБАБ, АБАБАБАБ, АБАБАБАБАБАБАБАБ,… };

14) L ₁₄ = {АБАБ, АБАБАБ, АБАБАБАБАБАБ, …};

15) L₁₅= {, А, Б, В, АА, ББ, ВВ};

16) L₁₆= {, АБ, АВ, АА, ААА, АААА,…}.

Необхідно задати кожну мову граматикою, що її породжує.

Розв’язок:

L₄ ={,АА, АБ, ВА, БА, ВАА, БАА, ВААА, БААА, …};

Граматика, що породжує цю мову G = <{d₀, d₁ ,d₂, d₃ }, {А,Б,В}, P, d₀ >, де множина Р містить такі правила:

d₀  Аd₁

d₁  Ad₄

d₀  Ad₂

d₂  Б d₄

d₀  Вd₃

d₀  Бd₃

d₃  Ad₃

d₃  Ad₄

d₄  