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 $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 konkatenasiyası deyilir.Deməli,hər bir söz simvolların konkatenasiyasıdır.

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

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

Fərz edək, ixtiyari $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:

$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 $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: $\{e\}\circ L_{1}=L_{1}\circ \{e\}=L_{1}$.
2. Kommutativliyin doğru olmaması: $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: $(L_{1}\circ L_{2})\circ L_{3}\equiv L_{1}\circ (L_{2}\circ L_{3})$.
4. Dilin boş çoxluqla konkatenasiyası: $\{\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.

$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. $\vert w\vert =k$ yazılışı ona göstərir ki, $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:$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: $1\cdot 2^{1}+2\cdot 2^{0}=4$ .

"aba" sözünün nömrəsi: $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
-	$3^{0}$	$3^{1}$	$3^{2}$	$3^{3}$

$9+9+2=20$ .

Cavab: $w='acb'$.

$w$ sözünün nömrəsi: $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ə metadil 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>.
3. Son şərtli dövr operatoru: Repeat<dövrün gövdəsi>until<şərt>.

Formal dili yaratmaq üçün düzgün sözlərin qurulması qaydaları verilməlidir. Bunun üçün aşağıdakı üsullar mövcuddur:

1. Düzgün sözlərin tam siyahısı verilir.
3. Sözlərin filtrasiyası(tanınması) qaydası verilir.
5. Dilin qurulması qaydası üçün formal qrammatika verilir.

Formal dilin sözlərini yaradan zaman rabitə vasitələrindən istifadə olunur. Fərz edək ki, söz qurmaq üçün rabitə vasitələri aşağıdakılardır:

o→ (sözün başlanğıcı)

→ (sözün ortası)

→o (sözün sonu)

Onda "then" sözünü aşağıdakı kimi qura bilərik:

o→t→h→e→n→o

Cömləni qurmaq üçün başqa rabitə vasitələrindən istifadə etmək olar:

o$\Rightarrow$ (cümlənin əvvəli)

$\Rightarrow$ (cümlənin ortası)

$\Rightarrow$o (cümlənin sonu)

Onda "then goto" cümləsini aşağıdakı kimi qura bilərik:

o$\Rightarrow$(o→t→h→e→n→o)$\Rightarrow$(o→g→o→t→o→o)$\Rightarrow$o

Göründüyü kimi, cümlə quran zaman bu vasitələrdən başqa mötərizələrdən də istifadə olundu. Mötərizə vasitələrinə cümlənin ayrı-ayrı konstruksiyalarını yaradan element kimi baxmaq lazımdır. Belə elementlərə formal dildə çərçivə deyilir. Əgər çərçivələrin özü də çərçivəyə alınarsa, onda daha mürəkkəb konstruksiyalar yaratmaq mümkündür. Məsələn, mürəkkəb cümlə sadə cümləyə nisbətən mürəkkəb konstruksiya kimi qiymətləndirilə bilər. Konstruksiyaların satsız-hesabsız formaları var, məsələn, matris tipli, ağac tipli və s. Sözü ən sadə informasiya modeli kimi qəbul etmək olar. A əlifbasında qurulmuş L formal dili olaraq ixtiyari sayda sözlər başa düşülür. Bu çoxluq sonlu, boş, hətta sonsuz ola bilər. Formal dil sonsuz olarsa, onun sözlərinin hər birini qurub yadda saxlamaq qeyri-mümkündür, bu halda insanın köməyinə formal qrammatika gəlir.

Məntiqi-riyazi formal dillər

İlk formal dil çoxluqlar nəzəriyyəsində və riyazi məntiqdə ifadə olunmuşdur. Bu elm sahələri aksiomlar üzərində qurulur və teoremləri formal isbat etməyə imkan verir. Məsələn, riyazi məntiqdən $\neg (A\wedge B)\equiv \neg A\vee \neg B$ düsturunu aşağıdakı kimi formal isbat etmək olar.Bunun üçün bərabərliyin sağ və sol tərəfləri üçün həqiqilik cədvəlini quraq. Sonuncu sütunların cavabları eynidir, bu da eyniliyi isbat edir.

A	B	$A\land B$	$\neg (A\land B)$
0	0	0	1
0	1	0	1
1	0	0	1
1	1	1	0

A	$\neg A$	B	$\neg B$	$\neg A\lor \neg B$
0	1	0	1	1
0	1	1	0	1
1	0	0	1	1
1	0	1	0	0

Məntiqi-riyazi formal dillərdə ən mühüm ifadələr termlər və düsturlardır. Term- obyektlərin adının analoqudur, bunun mahiyyəti obyekti qeyd etmək üçündür. Termlər dəyişən və sabitləri qeyd etmək üçün istifadə oluna bilər. Termlərdən yeni daha mürəkkəb termlər yaratmaq olar, bunun üçün, adətən, dilin funksiyalarından istifadə olunur.

Riyazi məntiqdə istifadə olunan inversiya($\neg$), konyuksiya ($\land$), dizyuksiya ($\lor$), implikasiya (⇒) və s. əməllərdən istifadə etməklə müxtəlif termlər qurmaq olar: $A$;$\neg (A\lor \neg C)$; $A\land B\to \neg A$ və s.

Paskal proqramlaşdırma dilində istifadə olunan termlərə aid nümunələr:

A;prog_1;((A1+25)>3*B)and(B>0));2+sqrt(z*sin(b)).

Formal dilin düsturları dilin operatorlarının termlərə tətbiqi ilə qurulur. Paskal dilində "düsturlara" aid bəzi nümunələrə baxaq:

A:2+sqrt(Z*sin(B)); if F>3 then write(R) else R:sqrt(F);

Term və düsturlar yeni ifadələrin yaradılması, çevrilməsi, başa düşülməsi üçün aşağıdakı ümumi qaydalardan istifadə etmək zəruridir:

1. Term və düsturların qurulması qaydaları
2. Term və düsturların interpretasiyası qaydaları(dlin semantikası)
3. 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