Formal diLLƏr və avtomatlar nəZƏRİYYƏSİ

5.7.3. Mili avtomatından Mur avtomatına və əksinə keçid
Mili və Mur avtomatlarının reaksiya çoxluqları üst-üstə düşür:

L(M) = {q_z | q_Z ∈ K};

L(U) = {h_t | h_t ∈ K₁};

L(M) = L(U).

Teorem.Hər bir Mur avtomatı üçün eyni gücdə olan Mili avtomatını qurmaq olar

İsbatı.Eyni gücdə olan M Mili avtomatının qrafı o zaman alınır ki, U Mur avtomatının hər bir tilinə M avtomatının tili uyğun gəlsin.

Tutaq ki,w = x₁ x₂ ... x_n – giriş zənciridir,onda M və U avtomatlarının reaksiya çoxluqları uyğun olaraq aşağıdakı kimi təsvir olunacaqdır:

q₀ / y₁, x₁ → q₁ / y₂, x₂ → ... → q_n-1 / y_n, x_n;

q₀, x₁ / y₁ → q₁, x₂ / y₂ → ... → q_n-1, x_n / y_n.

Teorem.Hər bir Mili avtomatı üçün ekvivalent Mur avtomatını qurmaq olar

İsbatı.Mur avtomatının K₁ çoxluğu şəklində K1 = K ⋅ Y –ni götürək M = U avtomatlarının bərabərliyi üçün keçidlər və cıxışlar funksiyalarını aşağıdakı şəkildə təyin edə bilərik:

f₁(p ⋅ y, a) = {qb | f(p, a) = q, b ∈ X};

h(p ⋅ y) = y.

Əgər M avtomatının w = x₁ x₂ ... x_n şəklində giriş zəncirinə reaksiyası q₀ vəziyyətində aşağıdakı kimi olur:

q₀, x₁ / y₁ → q₁, x₂ / y₂ → ... → q_k-1, x_k / y_k (1),

Onda determinə olmayan U avtomatının q0⋅x1 vəziyyəti var və bu vəziyyətdən öz işini başlayaraq U avtomatı aşağıdakı hərəkətləri yerinə yetirir:

q₀ ⋅ x₁ / y₁ → q₁ ⋅ x₂ / y₂ → ... → q_k-1 ⋅ x_k / y_k, x_k (2).

Analoji olaraq da tərs teoremi isbat etmək olar ki, (2) reaksiyasından sonra (1) reaksiyası gəlir,bu da Mili və Mur avtomatlarının eynigüclü olduğunu təsdiqləyir.

Ə D Ə B İ Y Y A T
1. Алферова З.В. Теория алгоритмов. - М.: Статистика, 1973.

2. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода, компиляции. В 2 т. Т.

1, 2. - М.: Мир, 1980.

3. Брауэр В. Введение в теорию конечных автоматов. -М.: Радио и связь, 1987.

4. Гинзбург С. Математическая теория контекстно-свободных языков. - М.: Мир, 1970.

5. Гросс М., Лантен А. Теория формальных грамматик.- М.: Мир, 1971.

6. Крючкова Е.Н. Теория алгоритмов. - Барнаул; 1995.

7. Крючкова Е.Н. Теория формальных языков и автоматов. - Барнаул; 1996.

8. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. - М.:

Энергоатомиздат, 1988.

9. Любимский Э.3., Мартынюк В.В., Трифонов Н.П. Программирование. - М.: Наука,

1980.

10. Мелихов А.Н., Кодачигов В.И. Теория алгоритмов и формальных языков. - Таганрог;

1983.

11. Рейуорд - Смит В. Дж. Теория формальных языков. Вводный курс. - М.: Мир, 1988.