Чорней Р.К. Теорія автоматів

Подождите немного. Документ загружается.

1.11. Аналiз автоматiв-розпiзнавачiв. Теорема Клiнi

Далi для k = 2 маємо

(2)

= (x

)

∪ ∅(e)

)

= (x

)

(2)

= ∅ ∪ ∅(e)

e = ∅,

(2)

= (x

)

∪ ∅(e)

∪ x

)

= (x

(2)

= x

)

∪ e(e)

)

= (x

)(x

)

(2)

= e ∪ e(e)

e = e,

(2)

= x

∪ x

)

∪ e(e)

∪ x

)

= x

∪ x

)

(2)

= ∅ ∪ x

(e)

)

= x

)

(2)

= x

∪ x

(e)

e = x

(2)

= e ∪ x

∪ x

(e)

∪ x

)

= e ∪ x

∪ x

)

Отже,

(3)

= ∅ ∪ (x

)

e ∪ x

∪ x

)

= (x

)

∪ x

)

(3)

= (x

)

∪ (x

)

e ∪ x

∪ x

)

e ∪ x

∪ x

)

= (x

)

∪ x

)

Таким чином, зображувана автоматом A подiя P описується регулярним виразом

)

∪ x

)

(e ∪ x

Теорема 1.1 (Теорема Клiнi). Подiя P зображується у скiнченному автоматi

тодi й тiльки тодi, коли вона регулярна.

Задачi до роздiлу 1

1. Побудувати таблицi переходiв i виходiв, граф, матрицi переходiв i виходiв ав-

томата Z, що реалiзує три операцiї зсуву трирозрядного двiйкового коду на одну

позицiю. Вхiднi сигнали визначають характер операцiї зсуву:

— логiчний зсув влiво (або вправо);

— арифметичний зсув вправо;

— циклiчний зсув вправо (або влiво).

Вихiдним є сигнал, що виходить за межi розрядної сiтки.

Стани вiдповiдають восьми можливим варiантам кодiв.

2. Побудувати таблицi переходiв i виходiв, граф, матрицi переходiв i виходiв ав-

томата P , що за допомогою своїх станiв запам’ятовує три останнi символи (двiйковi

розряди), якi було подано на його вхiд. Вихiдним сигналом є останнiй символ, що

«забувається».

3. Побудувати таблицi переходiв i виходiв, граф, матрицi переходiв i виходiв ав-

томата A, який переходить у стан T , якщо на його вхiд було подано послiдовнiсть

символiв, що вiдповiдає iдентифiкатору деякої мови програмування, i переходить у

стан H в противному разi. Вхiдними сигналами автомата A є такi: x

— лiтера, x

—

цифра, x

— будь-який iнший символ.

Роздiл 1. Теорiя автоматiв

4. Побудувати таблицi переходiв i виходiв, граф, матрицi переходiв i виходiв ав-

томата A, який переходить у стан T , якщо на його вхiд було подано послiдовнiсть

символiв, що вiдповiдає числовiй константi — дiйсному числу зi знаком i фiксованою

точкою, i переходить у стан H в противному разi. Вхiдними сигналами автомата A

є такi: x

— знак, x

— цифра, x

— точка, x

— будь-який iнший символ.

5. Побудувати автомат затримки, тобто автомат, вихiдний сигнал якого в момент

часу t + 1 дорiвнює вхiдному сигналу в момент часу t, X = Y = {0; 1} , y(0) = 0.

6. Побудувати автомат затримки на два такти, в якому вихiдний сигнал у мо-

мент часу t + 2 збiгається з вхiдним сигналом у момент часу t, X = Y = {0; 1},

y(0) = y(1) = 0.

7. Побудувати автомат для X = Y = {0; 1}, на виходi якого з’являється сигнал 1

тодi й лише тодi, коли чотирма останнiми вхiдними сигналами є «0110».

8. Побудувати «генератор парностi», тобто автомат, що функцiонує в алфавiтах

X = Y = {0; 1} i реалiзує такий алгоритм. На його вхiд надходять слова, в яких пiсля

кожної трiйки символiв стоїть 0. На виходi автомат повинен повторити вхiдну трiйку

символiв, замiнивши роздiловий 0 на 1 тодi й лише тодi, коли кiлькiсть одиниць у

цiй трiйцi парна.

9. Побудувати автомат для X = Y = {0; 1}, що порiвнює за величиною два до-

датних двiйкових числа однакової розрядностi. Пари розрядiв порiвнюваних чисел

подаються на вхiд автомата, починаючи зi старших розрядiв. Вихiдним словом по-

винно бути бiльше з цих чисел.

10. Побудувати автомат, що керує роботою лiфта в чотириповерховому будинку.

Станами автомата є номери поверхiв. Вхiдний сигнал — це номер потрiбного поверху,

вихiдний — напрямок руху (вгору, вниз, не рухатися).

11. Для автомата A, граф якого зображено на рис. 1.16, визначити вихiднi слова,

що є результатами автоматного вiдображення на заданному вхiдному словi.

²²

Рис. 1.16. Граф автомата A

1) а) ϕ

), б) ϕ

);

2) а) ϕ

), б) ϕ

);

3) а) ϕ

), б) ϕ

);

4) а) ϕ

), б) ϕ

);

5) а) ϕ

), б) ϕ

);

6) а) ϕ

), б) ϕ

);

7) а) ϕ

), б) ϕ

);

1.11. Аналiз автоматiв-розпiзнавачiв. Теорема Клiнi

8) а) ϕ

), б) ϕ

);

9) а) ϕ

), б) ϕ

);

10) а) ϕ

), б) ϕ

12. Довести, що в автоматi A = (X, Y, U, δ, λ) для довiльного вхiдного слова

p = p

∈ X

i будь-якого стану a

∈ U виконуються рiвностi

, p

) = δ

, p

), p

, p

) = λ

, p

), p

13. Методом математичної iндукцiї за довжиною слова p

довести таку власти-

вiсть автоматних вiдображень ϕ

, якi реалiзує автомат A = (X, Y, U, δ, λ): якщо

p = p

∈ X

, a

∈ U i a

= δ

, p

), то

) = ϕ

)ϕ

14. Довести умови автоматностi для автоматного вiдображення ϕ

15. Довести, що коли iснує гомоморфiзм γ автомата A

= (X, Y, U

, δ

, λ

) на авто-

мат A

= (X, Y, U

, δ

, λ

), то автомати A

i A

невiдрiзнюванi.

16. Довести, що коли для автомата A

iснують гомоморфiзми на автомати A

i A

то автомати A

i A

невiдрiзнюванi.

17. Довести, що iзоморфнi автомати є невiдрiзнюваними (еквiвалентними) мiж со-

бою.

18. Побудувати приклад двох невiдрiзнюваних автоматiв, якi не є iзоморфними.

19. Довести, що коли графи автоматiв A i B сильно зв’язнi й iснують невiдрiзнюванi

стани a

в автоматi A i b

в автоматi B, то A i B невiдрiзнюванi автомати.

20. Довести, що коли графи автоматiв A i B сильно зв’язнi й автомати A i B не є

невiдрiзнюваними, то жоден зi станiв автомата A не є невiдрiзнюваним з будь-яким

станом автомата B.

21. Перевiрити невiдрiзнюванiсть (еквiвалентнiсть) двох заданих сумiщеними та-

блицями переходiв/виходiв скiнченних автоматiв A

i A

а) A

/λ

1 2 3 4 5 6 7 8 9

3/1 3/2 3/2 5/2 3/1 1/2 8/2 3/1 3/2

6/1 7/1 7/2 6/2 7/1 6/2 7/2 4/1 4/1

3/2 6/2 3/1 2/1 3/2 9/1 2/1 3/2 4/2

/λ

1 2 3 4 5 6 7

7/2 6/2 7/2 7/2 6/2 6/2 6/1

1/2 1/1 4/2 3/2 4/1 1/2 4/1

5/1 3/2 2/1 2/1 1/2 6/1 6/2

Роздiл 1. Теорiя автоматiв

б) A

/λ

1 2 3 4 5 6 7 8 9

3/2 8/1 7/1 2/2 9/2 3/2 3/2 2/2 8/1

4/1 7/2 7/2 1/1 5/1 1/1 7/1 8/1 8/2

9/1 1/2 6/2 3/1 9/1 2/1 1/1 4/1 6/2

/λ

1 2 3 4 5 6 7

4/2 7/2 4/2 2/1 4/2 4/2 3/1

1/1 2/1 6/1 5/2 6/1 3/1 2/2

7/1 1/1 1/1 1/2 1/1 1/1 1/2

в) A

/λ

1 2 3 4 5 6 7 8 9

6/1 6/2 1/2 5/2 6/1 6/2 8/2 6/1 6/2

3/1 7/1 3/2 3/2 7/1 7/2 7/2 4/1 4/1

6/2 3/2 9/1 2/1 6/2 6/1 2/1 6/2 4/2

/λ

1 2 3 4 5 6 7

6/2 6/2 4/2 6/1 4/2 6/2 4/2

7/1 5/1 7/2 7/1 5/2 5/2 3/2

5/2 3/2 2/1 6/2 1/1 6/1 2/1

г) A

/λ

1 2 3 4 5 6 7 8 9

3/2 7/1 8/1 2/2 9/2 3/2 2/2 3/2 7/1

4/1 8/2 8/2 1/1 5/1 1/1 7/1 8/1 7/2

9/1 1/2 6/2 3/1 9/1 2/1 4/1 1/1 6/2

/λ

1 2 3 4 5 6 7

7/2 4/2 4/2 1/1 4/2 4/2 3/1

1/1 2/1 6/1 5/2 6/1 3/1 1/2

2/1 7/1 2/1 2/2 2/1 2/1 2/2

22. Довести, що у множинi K всiх невiдрiзнюваних мiж собою скiнченних автоматiв

iснує один i з точнiстю до iзоморфiзму тiльки один мiнiмальний автомат Z. Для

кожного автомата A ∈ K iснує гомоморфiзм γ на автомат Z.

23. Довести, що мiнiмальний автомат Z має найменшу можливу кiлькiсть станiв

серед усiх автоматiв класу K.

24. Довести справедливiсть твердження, оберненого до твердження попередньої за-

дачi: якщо автомат Z з класу K всiх невiдрiзнюваних мiж собою скiнченних авто-

матiв має найменшу можливу кiлькiсть станiв серед усiх автоматiв класу K, то Z —

мiнiмальний автомат.

1.11. Аналiз автоматiв-розпiзнавачiв. Теорема Клiнi

25. Довести, що мiнiмальнi автомати з того самого класу K невiдрiзнюваних авто-

матiв iзоморфнi мiж собою.

26. Довести, що мiнiмальнi автомати невiдрiзнюванi тодi й тiльки тодi, коли вони

iзоморфнi.

27. Довести, що коли стани a

, a

∈ U k-невiдрiзнюванi, (a

, a

) ∈ H

, то a

i a

будуть l-невiдрiзнюваними, (a

, a

) ∈ H

, для l < k.

28. Довести, що стани a

, a

∈ U автомата A невiдрiзнюванi тодi й тiльки тодi, коли

вони k-невiдрiзнюванi для будь-якого k = 1, 2, ...

29. Довести, що для фактор-множин за вiдношенням k-невiдрiзнюваностi H

вико-

нується нерiвнiсть |Q

| 6 |Q

k+1

|, k = 1, 2, ...

30. Довести, що коли в автоматi A = (X, Y, U, δ, λ) для фактор-множини за вiдно-

шенням k-невiдрiзнюваностi H

виконується нерiвнiсть |Q

| 6= |Q

k+1

|, то |Q

| > k + 1.

31. Довести, що стани a

та a

автомата A = (X, Y, U, δ, λ) вiдрiзнюванi тодi i тiльки

тодi, коли iснує слово p ∈ X

довжини не бiльше |U| − 1, для якого ϕ

(p) 6= ϕ

(p).

32. Довести, що для довiльного автомата A iз s станами виконуються рiвностi

s−1

= H i Q

s−1

= Q.

33. Нехай стани a

та a

автомата A iз s станами k

-невiдрiзнюванi i для довiльного

вхiдного слова w довжини k

стани a

= δ

, w) i a

= δ

, w) — k

-невiдрiзнюванi.

Довести, що коли k

+ k

> s − 1, то стани a

та a

— невiдрiзнюванi.

34. Побудувати автомат Мура, еквiвалентний заданому автомату Мiлi:

а) δ 1 2 3 λ 1 2 3

2 2 1 x

1 2 1

1 3 1 x

2 1 1

б) δ 1 2 3 λ 1 2 3

3 2 3 x

2 1 1

1 1 2 x

1 1 2

в) δ 1 2 3 λ 1 2 3

2 1 3 x

1 2 2

1 3 2 x

1 1 2

г) δ 1 2 3 λ 1 2 3

2 2 1 x

2 2 1

3 1 2 x

2 1 2

ґ) δ 1 2 3 λ 1 2 3

1 2 3 x

2 2 1

3 2 1 x

1 1 1

Роздiл 1. Теорiя автоматiв

д) δ 1 2 3 λ 1 2 3

2 1 3 x

1 2 1

1 3 2 x

2 1 1

е) δ 1 2 3 λ 1 2 3

3 1 2 x

1 2 2

1 3 2 x

1 1 2

є) δ 1 2 3 λ 1 2 3

2 2 1 x

2 2 1

1 3 2 x

1 2 2

ж) δ 1 2 3 λ 1 2 3

2 1 3 x

2 2 1

3 2 1 x

2 1 2

з) δ 1 2 3 λ 1 2 3

3 2 1 x

1 2 2

1 3 3 x

1 1 2

35. Побудувати (синтезувати) автомат-перетворювач Мура A = (X, Y, U, δ, µ) для

X = Y = {0, 1}, що реалiзує таке автоматне вiдображення ϕ

(1)

. . . x

) =

= y

. . . y

• y(0) = y(1) = 1, y(t + 2) = x(t);

• y

= 1, якщо в словi x

. . . x

одиниць менше, нiж нулiв, в противному разi

= 0;

• y

= 1 тодi й лише тодi, коли в словi x

. . . x

кiлькiсть одиниць парна;

• y

= 1, якщо x

. . . x

мiстить l одиниць, у противному разi y

= 0;

• y

= 1, якщо в словi x

. . . x

кiлькiсть одиниць кратна трьом, в против-

ному разi y

= 0;

• y

= 1 тодi й лише тодi, коли в словi x

. . . x

кiлькiсть одиниць кратна l.