Formal dillər

Formal dillər — insanın müxtəlif fəaliyyət sahələri üçün yaradılmış və öz əlifbası, qrammatik qaydaları, sintaksisi olan xüsusi dillərdir. Riyazi məntiq və riyazi proqramlaşdırma dillərini formal dillərə aid ən önəmli nümunələr olaraq qeyd etmək olar. Formal dillərin hamısı müəyyən şəxslər tərəfindən yaranıb. Formal dillər elm və texnikada geniş istifadə olunur.Elmi tətqiqatlarda və praktiki fəaliyyətdə formal dillər təbii dillərlə paralel istifadə olunur. Bunlardan biri digərini tam əvəz edə bilməz. Təbii dil daha güclü ifadə imkanlarına malik olsa da,formal dil biliyin daha dəqiq təqdimatı cəhətdən üstündür.

Tarixi

Riyaziyyatın bütün inkişaf tarixində müxtəlif obyektləri və anlayışları işarə etmək üçün həmişə simvolik işarələrdən istifadə olunmuşdur.Lakin işarələrdən başqa hər zaman təbii dillərdən də istifadə olunmuşdur.Elmin inkişafının müəyyən mərhələsində,əsasən ΧVΙΙ əsrdən başlayaraq,riyazi analizin ciddi məntiqi təhlilini və teoremlərin hökmlərini əsaslandırmaq üçün yeni bir yanaşmaya ehtiyac yarandı.Riyazi nəzəriyyələrin ciddi formalarla təqdimatı olmadan bir sıra məsələlərin həllinin mümkünsüzlüyü aydın oldu.Beləliklə,ΧΧ ərdən etibarən formal dillər yaranmağa başladı.

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

Dil, onun əlifbası və söz

Hər bir dil informasiyanı qarşı tərəfə çatdırmaq üçün istifadə olunur.Qarşı tərəf dedikdə insan,kompüter və s. nəzərdə tutulur.Dil informasiyanı birbaşa,yaxud dolayı yolla çatdırır.Dillər sintaksis və semantikadan ibarət olur.Sintaksis cümlənin quruluşunu müəyyənləşdirmək üçün istifadə olunur,semantika isə cümlənin mənasını müəyyənləşdirir.Semantika sözlərin və cümlələrin məzmununu düzgün qurmağa xidmət edir.Simvollar çoxluğuna əlifba deyilir,əlifba-simvolların nizamlanmış çoxluğudur.Əlifbaya ixtiyari simvollar:hərflər,ədədlər,heroqliflər,yol nişanları və s. daxil ola bilər.Simvolların müəyyən sintaksis qaydalar ilə düzülüşündən əmələ gələn konstruksiyaya söz deyilir.Sözdəki simvolların sayına sözün uzunluğu deyilir.Tutaq ki,A={a₁,a₂,…,a_n} hər hansı əlifbadır.Verilmiş əlifbada bütün sonlu sözlərdən(yəni uzunluğu sonlu olan)ibarət çoxluğa universum deyilir,bunu A* ilə işarə edək.Aydındır ki,bu çoxluğun gücü hesabidir.Verilmiş B={0,1} əlifbasının universumu B*={0,1,00,01,10,11,000,001,…} olar.Heç bir simvolu olmayan sözə "boş söz" deyilir və {e} ilə işarə olunur.Universumdan {e} sözünün kənarlaşması ilə alınan çoxluq A⁺=A*\{e}.

Sözlər üzərində əməliyyatlar

Sözlərin konkatenasiyası(birləşdirilməsi) əməliyyatı

A əlifbasının A* universiumunda təyin olunmuş x,y sözlərinin verildiyini fərz edək: x=x₁,x₂,…,x_m,y=y₁,y₂,…,y_s, burada x_i,y_j∈A(i=1,…,m;j=1,…,s)m,s∈N. Onda ${\displaystyle x\circ y=x_{1}x_{2}....x_{m}y_{1}y_{2}...y_{s}}$sətirinə(sözünə) x və y sözlərinin deyilir.Deməli,hər bir söz simvolların konkatenasiyasıdır.

Konkatenasiya əməliyyatının xassələri:

1. ${\displaystyle e\circ x=x\circ e=x}$.
2. Kommutativliyin doğru olmaması: ${\displaystyle x\circ y\neq y\circ x}$. Misal1.x=ab,y=ba sözləri verilmişsə,onda ${\displaystyle x\circ y=abba}$ , ${\displaystyle y\circ x=baab}$ olar , yəni ${\displaystyle xy\neq yx}$ .
3. Assosiativlik:${\displaystyle (x\circ y)\circ z=x\circ (y\circ z)}$. Misal2.x=ab,y=ba,z=aa sözləri verilmişsə,onda ${\displaystyle (x\circ y)\circ z=abbaaa}$ , ${\displaystyle x\circ (y\circ z)=abbaa}$ olar , yəni ${\displaystyle (x\circ y)\circ z=x\circ (y\circ z)}$.

Fərz edək, ixtiyari ${\displaystyle x=\alpha \circ \beta \circ \gamma }$ sözü verilmişdir,burada α,β,γ konstruksiyaları A*-a daxil olan hər hansı sözlərdir.Onda α-prefiks,β-alt söz,γ-sufiks adlanır.

Tərif. A əlifbası üzərində qurulmuş L(A) formal dili dedikdə A* universal çoxluğunun ixtiyari alt çoxluğu başa düşülür: L(A)∈ A*.

Misal3.B={0,1} əlifbası üzərində L dili olaraq 0-dan 7-yə qədər ədədlərin kodunu qeyd etmək olar:

L(B)={0,1,01,10,11,100,101,110,111}, deməli L(B) dili 0-dan 7-yə qədər ədədlərin dilidir.

Formal dillər üzərində əməliyyatlar . İxtiyari L₁ və L₂ dillərinin konkatenasiyası aşağıdakı kimi başa düşülür:

${\displaystyle L_{1}\circ L_{2}=\{x\circ y\mid x\in L_{1},y\in L_{2}\}}$

Misal 4. L₁={ab,a}, L₂={α,βα} dilləri verilmişsə, onda ${\displaystyle L_{1}\circ L_{2}=\{ab\alpha ,ab\beta \alpha ,a\alpha ,a\beta \alpha \}}$, yəni qurulan dilin sözləri baza dillərinin sözlərinin konkatenasiyası ilə qurulur.

Dillər üzərində konkatenasiya xassələri:

1. Dilin "boş sözlə" konkatenasiyasının xassəsi: ${\displaystyle \{e\}\circ L_{1}=L_{1}\circ \{e\}=L_{1}}$.
2. Kommutativliyin doğru olmaması: ${\displaystyle L_{1}\circ L_{2}\neq L_{2}\circ L_{1}}$.
3. Fərz edək, 3 dil verilmişdir: L₁,L₂,L₃∈ A*. Assosiativlik xassəsi: ${\displaystyle (L_{1}\circ L_{2})\circ L_{3}\equiv L_{1}\circ (L_{2}\circ L_{3})}$.
4. Dilin boş çoxluqla konkatenasiyası: ${\displaystyle \{\emptyset \}\circ L_{1}=L_{1}\circ \{\emptyset \}=L_{1}}$.

Göründüyü kimi, dillər üzərində konkatenasiya əməliyyatı çoxluqlar üzərində dekart hasil əməliyyatının eynisidir. Ümumiyyətlə, dillər üzərində əməliyyatlar çoxluqlar üzərində əməliyyatlara bənzəyir. Dillər üzərində birləşdirmə, kəsişmə, çıxma və s. əməliyyatlar aparmaq olar.

Dilin iterasiyası dedikdə bu dilin bütün qüvvələrinin birləşməsi başa düşülür.

${\displaystyle L^{*}=\bigcup _{i=0}^{\infty }L^{i}}$

L* dilinə A əlifbasının verilmiş L dilinin Klini qapanması deyilir. Verilmiş əlifbadan istifadə etməklə müxtəlif uzunluqlu sözlər qurmaq olar. Sözün uzunluğu dedikdə bu sözdə iştirak edən simvolların sayı başa düşülür. ${\displaystyle \vert w\vert =k}$ yazılışı ona göstərir ki, ${\displaystyle w}$ ilə işarə edilmiş sözün uzunluğu k ədədinə bərabərdir. Fərz edək, V^k — k uzunluqlu sözlər çoxluğudur, V^* — həmin dildə mövcud olan bütün sözlər çoxluğudur. Onda yaza bilərik:${\displaystyle V^{k}\subset V^{*}}$ .

V={a,b} əlifbasına baxaq. Bu simvollardan müxtəlif sözlər düzəltmək olar:a,b,aa,ab,ba,bb,aaa,…

Göstərmək olar ki, hər bir sözə qarşı onun birqiymətli olaraq nömrəsini hesablamaq olar, məsələn, ab sözünün nömrəsini hesablamaq üçün əvvəlcə simvolların özlərini nömrələyirlər: a-1, b-2,…

"ab" sözünün nömrəsi: ${\displaystyle 1\cdot 2^{1}+2\cdot 2^{0}=4}$ .

"aba" sözünün nömrəsi: ${\displaystyle 1\cdot 2^{2}+2\cdot 2^{1}+1\cdot 2^{0}=9}$ .

Əksinə, verilmiş nömrəyə görə sözün tapılması qaydasına baxaq: V={a,b,c} əlifbasında 20 nömrəli sözü tapmaq tələb olunur.

a	1	3	9	27
b	2	6	18	54
c	3	9	27	81
-	${\displaystyle 3^{0}}$	${\displaystyle 3^{1}}$	${\displaystyle 3^{2}}$	${\displaystyle 3^{3}}$

${\displaystyle 9+9+2=20}$ .

Cavab: ${\displaystyle w='acb'}$.

${\displaystyle w}$ sözünün nömrəsi: ${\displaystyle 1\cdot 3^{2}+3\cdot 3^{1}+2\cdot 3^{0}=20}$ .

Formal dildə cümlə

Sözlərdən əmələ gələn daha mürəkkəb konstruksiyaya cümlə deyilir. Hər bircümlənin yalnız bir mənası ola bilər. Ona görə də insan dili bütövlükdə heç vaxt proqramlaşdırmada istifadə oluna bilməz, çünki insan dilində çoxmənalı, dolaşıq cümlələr mövcuddur ki, bunları kompüter başa düşə bilməz. Hər bir dil fikri ifadə etməyə xidmət edir. Dil fikri birbaşa, ya da dolayısı ilə ifadə edə bilir. Şifahi dil adətən fikri birbaşa ifadə edə bilir. Yazılı dil isə fikri yox, şifahi dilin səslərini ifadə edir, məsələn biz "at" sözünün yazanda fikrimizdə olan canlının özünü yox onun Azərbaycan dilindəki səslərini kodlaşdırırıq. Deməli, yazılı dilin ierarxiyası iki mərtəbədən ibarətdir. Lakin yazılı dil bir mərtəbəli ola bilər. Məsələn, at şəklini çəkməklə canlının özünü yazı ilə kodlaşdırmaq olar. Üç mərtəbəli yazılı dilə aid misal olaraq Morze əlifbasını göstərmək olar. Morze əlifbası ilə insan dilinin hərfləri kodlaşdırılır(1-ci mərtəbə), hərflərlə dilin sözləri kodlaşdırılır(2-ci mərtəbə), sözlərlə fikir kodlaşdırılır(3-cü mərtəbə). Maşın dilləri bir mərtəbəli dillərdir. Universal dillər iki mərtəbəlidir. Yuxarı qatda olan dilə deyilir.Yəni universal dil maşın dilinə nəzərən metadildir. Formal dilin qurulması üçün birincisi sintaksis, ikincisi isə semantika qaydaları verilməlidir. Bu zaman aşağıdakı şərtlər irəli sürülür:

• Sintaksis semantikadan asılı olmamalıdır
• Hər cümlənin yalnız bir mənası ola bilər. Lakin müxtəlif cümlələr eyni məna verə bilər. Məsələn, Paskal dilində dövr operatorunun iki fərqli yazılışına baxaq:

1. Ön şərtli dövr operatoru: While<şərt>do<dövrün gövdəsi>.
2. Son şərtli dövr operatoru: Repeat<dövrün gövdəsi>until<şərt>.
3. Sözlərin filtrasiyası(tanınması) qaydası verilir.
4. Dilin qurulması qaydası üçün formal qrammatika verilir.
5. Term və düsturların interpretasiyası qaydaları(dlin semantikası)
6. Term və düsturlardan yeni term və düsturların qurulması qaydaları

Hər bir formal dildə bu qaydalara ciddi riayət etmək tələb olunur və bunlardan hər hansı birinin modifikasiyası formal dilin yeni versiyasının(dialektinin) qurulması ilə nəticələnir.

Həmçinin bax

• Alqoritmlər

İstinadlar

1. Vaqif Əsəd oğlu Kərimov. Alqoritmlər nəzəriyyəsi. Dərs vəsaiti. Bakı. ADNSU-nun nəşri, 2017.