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

f (x_1, x_2, ...,x_n ,0 )= g(x_1, x_2, ...,x_n) (2)

f (x_1, x_2, ...,x_n ,y+1 )= h(x_1, x_2, ...,x_n,y,
(2) bərabərliyi primitiv rekursiya sxemi adlanır.

Primitiv rekursiya əməliyyatını başa düşmək üçün qeyd etmək lazımdır ki,az saylı arqumenti olan istənilən funksiyanı çox saylı arqumenti olan funksiya kimi baxmaq olar.Primitiv rekursiya operatorunda əsas əhəmiyyət odur ki,f funksiyasında dəyişənlərin sayından asılı olmayaraq, rekursiya y dəyişəninə görə aparılır.Digər x_1, x_2, ...,x_n dəyişənləri (2)-nin tətbiqi zamanı parametr rolunu oynayır.

2.2.3. Minimallaşdırma operatoru

P(x_1, x_2, ...,x_n) münasibəti o vaxt primitiv-rekursiv adlanır ki,əgər onun xarakterik funksiyası primitiv-rekursivdir:

0 əgər P(x_1, x_2, ...,x_n) - “səhv”

Χ(x_1, x_2, ...,x_n)=

1 əgər P(x_1, x_2, ...,x_n) -“doğru”

Predikat o vaxt primitiv rekursiv olur ki,əgər onun xarakterik funksiyası primitiv-rekursivdir. f (x_1, x_2, ...,x_n) funksiyası P(x_1, x_2, ...,x_n,z) ,predikatından minimallaşdırma operatorunun köməyilə alınır,əgər f (x_1, x_2, ...,x_n) funksiyasının istənilən qiymətində z minimal qiyməti olursa,onda P(x_1, x_2, ...,x_n,z) predikatı “doğruya” çevrilir:
f (x_1, x_2, ...,x_n) = μ_z (P(x_1, x_2, ...,x_n,z)),
haradaki, μ_z-minimallaşdırma operatorudur.
2.2.4.Minimallaşmanın məhdudiyyət operatoru
P(x_1, x_2, ...,x_n,z) predikatından və U (x_1, x_2, ...,x_n) funksiyasından minimallaşmanın məhdudiyyət operatoru o zaman alınır ki,istənilən nöqtədə bu funksiyanın qiyməti aşağıdakı kimi təyin olunsun:

1) ixtiyari z< U (x_1, x_2, ...,x_n) üçün P(x_1, x_2, ...,x_n,z) = “doğru”dur və funksiyanın qiyməti

2)qeyri-ixtiyari z< U (x_1, x_2, ...,x_n) üçün P(x_1, x_2, ...,x_n,z) = “doğru”dursa,funksiyanın qiyməti f (x_1, x_2, ...,x_n) = U (x_1, x_2, ...,x_n).

Bu aşağıdakı kimi yazılır:

f (x_1, x_2, ...,x_n) = μ_z(P(x_1, x_2, ...,x_n,z))

z məhdudiyyəti minimallaşmanın məhdudiyyət operatorunda hesablamaların sona çatması üçün zəmanət verir və P predikatların sayını göstərir.Hesablamaların sayının göstərilməsi imkanı primitiv- rekursiv funksiyanın əsas xüsusiyyətidir.

2.3. Primitiv- rekursiv funksiyalar

Hesablanan funksiyaların çoxu primitiv- rekursiv funksiyalar sinfinə aiddir.

Funksiya o vaxt primitiv- rekursiv adlanır ki,superpozisiya və primitiv-rekursiya operatorlarının son qiymətinin köməyilə sadə funksiyalardan alınsın.Əgər bəzi funksiyalar primitiv-rekursivdirsə,onda onlara superpozisiya və ya primitiv -rekursiv operatorlarını tətbiq etməklə yeni primitiv- rekursiv funksiyalar almaq olar.

Funksiyanın primitiv- rekursiv olmasını 3 cür isbat etmək olar:

1) Verilmiş funksiyanın sadə olduğunu sübut etməklə;

2) Verilmiş funksiyanın superpozisiya operatoru köməyilə qurulduğunu sübut etməklə;

3) Verilmiş funksiyanın primitiv- rekursiya operatoru köməyilə qurulduğunu sübut etməklə;

Bununla belə primitiv- rekursiv funksiyalar bütün hesablanan funksiyaları (hansılar ki,konstruktiv təyin oluna bilər) əhatə etmir.
2.4 .Rekursiv alqoritmlərin tipləri
Rekursiv alqoritmlərin qurulmasının effektivliyiaşağıdakı şərtlərlə təyin olunur:

1) Əgər ilkin verilənlər rekursiv struktura malikdirsə,onda belə strukturların analizinin proseduru daha effektiv olur,

2) Əgər ixtiyari verilənlər yığımının emalı alqoritmini qurarkən,verilənlər hissələrə bölsək və hər bir hissəni ayrı-ayrılıqda emal etsək,onda hissə-hissə alınmış cavablardan(həllərdən)ümumi bir cavab almış olarıq.

3) Əgər məsələnin həlli zamanı müxtəlif həllər çoxluğundan optimal variantı seçmək lazımdırsa,onda axtarılanhəll sonlu sayda addımlar vasitəsilə tapılacaqdır.Bu zaman hər bir addım zamanı informasiyanın bir hissəsi silinir və getdikcə məsələ daha az verilənlərlə həll olunur.Məsələnin həlli ya verilənlər qurtardıqdan sonra tapılır, ya da axtarılan həll cari verilənlər yığımından tapılır.