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

5.4.Requlyar çoxluqlar
Requlyar çoxluqlar formal dillər nəzəriyyəsi üçün əhəmiyyətli olan dillər sinfi yaradır.Dillərin verilmə metodlarına baxaq.Bunların hər biri requlyar çoxluq yaradır.Onlar arasında requlyar ifadələr,xətti qrammatikalar,determinə olan və determinə olmayan avtomatlar.

Tutaq ki, hər hansı avtomatdır.Requlyar şoxluqlar ∑ əlifbasında rekursiv olaraq aşağıdakı kimi olur.

1) 0 - boş çoxluq;

2) {ε} – boş zəncirdən ibarət çoxluq;

3) {a} - hər bir a ∈ Σ elementinə görə requlyar çoxluq;

4) əgər P və Q Σ əlifbasında requlyar çoxluqdursa,onda aşağıdakı çoxluqlar da requlyardır

а) P ∪ Q

b) PQ

c) P*.

Σ əlifbasında digər requlyar çoxluq yoxdur.Beləliklə,verilmiş Σ əlifbasında zəncirlərin bəzi çoxluqları ,ancaq və ancaq o zaman requlyar adlanır ki,əgər o, aşağıdakı çoxluqlardan biri olsun:0, {ε} və ya hər hansı a ∈ Σ üçün {a} , ya da bu çoxluqlara sonlu sayda birləşmə,konkatenasiya və iterasiya əməliyyatları tətbiq etməklə almaq olar.

Hər bir requlyar çoxluq üçün bu çoxluğu təsvir edən bir requlyar ifadə var.

Sonlu avtomat tərəfindən tanınan dil – ilkin vəziyyətlərdən son vəziyyətə keçərkən avtomat tərəfindən oxunan zəncirlər çoxluğudur

L(A)={a₁ a₂ ... a_n | p₀a₁ → p₁, p₁a₂ → p₂, ..., p_n-1a_n → p_n; p_n ∈ F}.

Çoxluq o zaman requlyar adlanır ki,onu tanıyan sonlu avtomat olsun.