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

FORMAL DİLLƏR VƏ AVTOMATLAR NƏZƏRİYYƏSİ
(mühazirələr konspekti)

MÜNDƏRİCAT
GIRIŞ

I.ALQORİTMLƏR NƏZƏRİYYƏSİNİN ƏSAS ANLAYIŞLARI

1.1.İlkin anlayışlar

1.2.Alqoritmlərə qoyulan əsas tələbatlar

2. 
   REKURSİV FUNKSİYALAR
   

2.1. Əsas anlayışlar

2.2. Sadə funksiyalar anlayışı

2.2.1.Superpozisiya operatoru

2.2.2.Primitiv rekursiya operatoru

2.2.3. Minimallaşdırma operatoru

2.2.4.Minimallaşmanın məhdudiyyət operatoru

2.3. Primitiv- rekursiv funksiyalar

2.4 .Rekursiv alqoritmlərin tipləri

III. TYURİNQ MAŞINLARI

3.1.Əsas məlumatlar

3.2.Tyurinq maşınlarının formal olmayan tərifi

3.3. Tyurinq maşınlarının formal tərifi

3.4. Tyurinq maşınının təsviredilmə üsulları

3.4.1. Əmrlərin birləşməsindən istifadə etməklə Tyurinq maşınların təsviri

3.4.2. Tyurinq maşınının qrafla təsviri

3.4.3. Tyurinq maşınının cədvəllə təsvir edilməsi

3.5. Hesablanan funksiyalar

3.6. Tyurinq maşını üzərində əməllər

IV.FORMAL QRAMMATİKALAR VƏ DİLLƏR.

4.1.Törəmə qrammatikanın əsas anlayışları

4.2 Qrammatikanın klassifikasiyası

4.3. KS qrammatikanın çevrilməsi

V.AVTOMATLAR NƏZƏRİYYƏSİ

5.1 Avtomat anlayışı.Avtomatların tipləri

5.2.Avtomatın formal tərifi

5.3. Dillər və avtomatlar

5.4.Requlyar çoxluqlar

5.5.Maqazin yaddaşlı avtomat

5.6.Cevirici anlayışı

5.7.Mili və Mur avtomatları

5.7.1.Mili avtomatı

5.7.2.Mur avtomatı

5.7.3. Mili avtomatından Mur avtomatına və əksinə keçid

Ə D Ə B İ Y Y A T

GIRIŞ
“Formal dillər və avtomatlar nəzəriyyəsi”fənni informatika və hesablama texnikasının əsas istiqamətlərindən olan kompyuter mühəndisliyinin öyrənilməsinin əsas tərkib hissələrindən biridir.

“Formal dillər və avtomatlar nəzəriyyəsi” sintaksis metodların fundamentini (əsasını) təşkil edir.Bu nəzəriyyənin əsasını XX əsrin 40-50-ci illərindətəbii dillərin öyrənilməsinə həsr olunmuş linqvistik işlərilə N.Xomskiy qoymuşdur.Sonrakı onilliklərdə isə sintaksis üsullar proqramlaşdırma dillərinin yaradılmasında və realizə olunma sahəsində geniş tətbiqini tapmışdır.

Hal-hazırda hər hansı bir sahəni mətnlə təsvir edən süni dillər nəinki proqramlaşdır-mada, digər sahədə də tətbiq edilir.Onların köməyilə real həyatda və modellərdə istifadə olunan istənilən hər hansı bir sənədin ,üç ölçülü virtual obyektin , qrafiki interfeyslərin ,bir çox digər sahələrin strukturu təsvir olunur.Belə mətn şəklində olan təsvirlərin korrekt(düzgün) tərtib edilməsi, daha sonra düzgün başa düşülməsi və interpretasiya olunması xüsusi analiz və çevrilmə metodlarından istifadə olunur.Bu metodların əsasında Formal dillər və avtomatlar nəzəriyyəsi durur.

Formal dillər və avtomatlar nəzəriyyəsi riyazi linqvistikanın inkişafına və təbii və suni dillərlə əlaqədar olan süni intellektin inkişafına yeni bir stimul verdi.Bundan başqa onun elementləri mətn şəklində deyil,2-k formatda verilmiş verilənlərin strukturu,faylların,şəkillərin təsviri zamanı müvəffəqiyyətlə tətbiq edilir.

I.ALQORİTMLƏR NƏZƏRİYYƏSİNİN ƏSAS ANLAYIŞLARI

1.1.İlkin anlayışlar

Riyaziyyatın əsas anlayışlarından biri olan alqoritm-hesablama maşınlarının yaranmasından xeyli əvvəl meydana gəlmişdi.Uzun əsrlər boyu insanlar alqoritm anlayışından intuitiv olaraq istifadə edirdilər.IX əsrdə Xarəzmdə (indiki Özbəkistanda ) yaşamış məşhur özbək riyaziyyatçısı Məhəmməd İbn Musa Əl-Xarəzm ilk dəfə belə bir ideyanı irəli sürmüşdür:istənilən riyazi və fəlsəfi məsələnin həlli mexaniki yerinə yetirilən qaydalar ardıcıllığı ilə tərtib rdilə bilər.Əl-Xarəzmin yazdığı traktatın XII əsrdə latın dilinə tərcümə olunması sayəsində avropalılar mövqeli say sistemi ilə tanış olmuş, onluq say sistemini və onun hesab qaydalarını alqoritm adlandırmışlar.Alqoritm sözü Əl –Xarəzmin latın əlifbası ilə olan “Alhorithm” yazılışına uyğun olaraq əmələ gəlmişdir.

Ümumiyyətlə , alqoritm – verilmiş məsələnin həlli üçün lazım olan əməliyyatları müəyyən edən və onların hansı ardıcıllıqla yerinə yetirilməsini göstərən formal yazılışdır.Hesablama maşınlarının əsas fərqləndirici xüsusiyyətlərindən biri də onun proqramla idarə olunmasıdır.Yəni, istər sadə, istərsə də mürəkkəb məsələni maşının həll etməsi üçün proqram tərtib edilməlidir.

Riyaziyyatda tipik məsələləri həll etdikdə biz, hərəkətlərin ardıcıllığını təsvir edən müəyyən qaydalardan istifadə edirik.Məsələn,kəsr ədədlərin toplanma qaydası, kvadrat tənliyin həlli və s.Adətən, istənilən təlimat və qaydalar özlüyündə ardıcıl hərəkətlərdən ibarət olur və onları müəyyən qaydada yerinə yetirmək lazımdır.Məsələni həll etmək üçün hansı hərəkətlərin və hansı ardıcıllıqla yerinə yetirilməsini bilmək lazımdır.Axtarılan nəticəni əldə etmək üçün verilənlər üzərində hərəkətlərin yerinə yetirilmə qaydasını təyin edən göstəriş və təlimatlar elə alqoritm deməkdir.

Alqoritm-sonlu sayda addımlar nəticəsində məsələnin həllini əldə etmək üçün icraçı tərəfindən yerinə yetirilən aydın və dəqiq müəyyən hərəkətlər ardıcıllığıdır.

Alqoritm anlayışı nəinki riyaziyyatın,həmçinin də müasir elmin əsas anlayışlarından biridir.

1.2.Alqoritmlərə qoyulan əsas tələbatlar
Hər bir tərtib olunan alqoritmin giriş, aralıq və çıxış verilənlərilə işi olur. Verilənlər də obyektlər kimi dəqiq təyin olunmalı və nəinki bir-birindən həm də digər informasiyalardan seçilməlidir.

Verilənlərin yerləşdirilməsi üçün yaddaş tələb olunur.Adətən yaddaş bircinsli və diskret olur.Verilənlərin və yaddaşın tutumunun ölçü vahidi uyğunlaşmışdır,amma yaddaş sonsuz ola bilər

Ümumi şəkildə desək, alqoritm məsələnin həll yoludur, yəni məsələnin həllini təmin edən formal qaydalar sistemidir. Məsələnin kompüterdə həlli baxımından alqoritm axtarılan cavabların alınması üçün məsələnin verilənləri üzərində icra olunan hesabi və məntiqi əməllər (mərhələlər) ardıcıllığıdır. Bu mərhələlərdə uyğun olaraq hesab və müqa­isə əməlləri yerinə yetirilir. Müqayisənin nəticəsindən asılı olaraq bu və ya digər mərhələ­in icrasına keçilir.

Alqoritm həll olunan məsələnin xarakteri ilə bağlı olduğu üçün onun yaradılmasında ümumi qaydalar yoxdur. Lakin hər bir alqoritm tərtib edilərkən onun müəyyən tələblərə cavab verməsi nəzərə alınmalıdır. Bu tələblərə alqoritmin xassələri deyilir. Alqoritmin aşağıdakı xassələri vardır:

1. 
   Müəyyənlik. Alqoritmin tərtibi məsələnin həllini ardıcıl yerinə yetirilən mərhələlərə bölmək deməkdir. Bu zaman əvvəlki mərhələlərin nəticələri sonrakı mərhələ­ə istifadə oluna bilər. Əsas tələb ondan ibarətdir ki, hər bir mərhələnin məzmunu və mərhə­ələrin yerinə yetirilmə ardıcıllığı müəyyən olmalıdır. Bu alqoritmin müəyyənlik xassəsini təşkil edir.
   
2. 
   Kütləvilik. Bu xassədə iki tələb nəzərdə tutulur:
   

a). müəyyən məsələnin həlli üçün qurulmuş alqoritm həmin tipdən olan bütün məsələlərin həlli üçün yararlı olmalıdır;

b). alqoritm elə təsvir olunmalıdır ki, ondan hamı istifadə edə bilsin.

3. Alqoritm diskret olmalıdır, yəni hesablama prosesi əməllər ardıcıllığına bölünməlidir.

4. Nəticəvilik. Alqoritmdəki mərhələlərin və onları təşkil edən əməliyyatların sayı sonlu olmalıdır ki, onların yerinə yetirilməsi axtarılan nəticəyə gətirib çıxara bilsin.

Alqoritmdəki hesab əməlləri arasındakı məntiqi əlaqələr kompüterin qəbul edə biləcəyi şəkildə verilməlidir. Həmin əlaqələr çox vaxt bu və ya digər hesablama addım­arının seçilməsini təyin edən müəyyən şərtlərin yoxlanması şəklində ifadə olunur. Məntiqi şərtlər içərisində aşağıdakılar xüsusi yer tutur, çünki onların yaranması hesablama prosesinin normal gedişinə imkan vermir:

• 
  hesablamada mütləq qiymətcə kompüterdə təsvir oluna biləcək maksimal ədəddən böyük ədədin alınması;
  
• 
  sıfırın və ya mənfi ədədin loqarifmalarının hesablanması;
  
• 
  mənasız hesablamaların aparılmasına cəhd göstərilməsi ( məsələn, olduqda, arcsin(x) və ya arccos(x) –in hesablanması).
  

3.