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

Requlyar dillər üzərində əməliyyatlar

Hər bir ixtiyari sonlu avtomata birmənalı determinə olmuş sonlu avtomat uyğun gəlir.Sonlu avtomatlar üzərindəki əməliyyatlar requlyar çoxluq və ya requlyar dillər üzərindəki əməllər ilə ekvivalentdir.

Məlumdur ki,ixtiyari sonlu avtomat üşün ilkin və son vəziyyətlərində tsiklsiz ekvivalent avtomat qurmaq olar.

Teorem İxtiyari sonlu avtomat üçün ilkin vəziyyətdə tsiklsiz sonlu avtomat var.

İsbatı. Tutaq ki, A = (К, ∑, δ, p₀, F) ixtiyari sonlu avtomatdır.Aşağıdakı avtomatı quraq:

A₁ = (K ∪ {q₀}, Σ, δ ∪ {q₀a → p_i | p₀a → p_i ∈δ}, q₀, F∪ {q₀ | p₀ ∈ F}).

İstənilən x=a₁a₂...a_k zənciri L(A) dilinə ancaq və ancaq o zaman aid olur ki, A avtomatının əmrləri aşağıdakı ardıcıllıqda olsun:

p₀a₁ → p₁; p₁a₂ → p₂; . . . ; p_h-1a_h → p_h, p_h ∈ F

və ona uyğun olaraq A₁ avtomatının əmrləri aşağıdakı ardıcıllıqda olsun:

q₀a₁ → p₁; p₁a₂ → p₂; . . . ; p_k-1a_k → p_h.

Beləliklə , A=A₁ olur.

Teorem. İxtiyari sonlu avtomat üçün son vəziyyətdə tsiklsiz sonlu avtomat var.

İsbatı. Tutaq ki,avtomatın ilkin vəziyyətdə tsiklləri yoxdur.Verilmiş A = (К, Σ, δ, p0, F) ixtiyari sonlu avtomatnı yeni A₁ avtomatı ilə müqayisə edək:

A1 = (K∪{f}, Σ, δ∪{q_ja → f | p_ja → p_i∈δ & p_i∈F}, p₀, {f}∪{p₀ | p₀ ∈ F}).

Nəticədə alarıq: , A=A₁