Biçimsel Diller

Biçimsel dil, günlük hayatta alışkın olduğumuz dil kavramının bir tür genellemesidir.

Temel Kavramlar

Başlangıç için biçimsel dili Türkçe gibi bildiğimiz bir dil olarak düşünebiliriz. Böyle bir dil nelerden oluşur? Sözcüklerden oluşur; sözcükleri de daha sonra cümleler hâlinde birleştiririz. Cümleler bizi ilgilendirmeyecek, yalnızca sözcüklerle ilgileneceğiz. Sözcükler nelerden oluşur? Alfabenin harflerinden. O hâlde işe alfabeyle başlayalım.

Alfabe, boş olmayan herhangi bir kümedir. Alfabenin elemanlarına sembol denir. Türkçeden söz ediyorsak bu, küçük ve büyük harflerin yanı sıra ç, ğ, ı, ö, ş, ü gibi özel harfleri de içeren olağan Türk alfabesi olur. Türkçeyi değil de örneğin sayıları yazmak isteseydik, alfabemizde on rakamın hepsi bulunurdu. Alfabeyi çoğu zaman Σ sembolüyle gösteririz.

Sözcük (dizge de denir), bir Σ alfabesinin sembollerinden oluşan sonlu bir dizidir. Örneğin Σ= {a,b,c,d,e,…, z} alfabesi verilmişse “merhaba” ya da “kedi” bir sözcüktür; ama “akşam” (“ş” harfi yok), “Ahmet” (“A” harfi yok) ya da “iyi gün” (“ü” harfi ve boşluk yok) sözcük değildir. Sözcüğün uzunluğu, sözcüğü oluşturan sembollerin sayısıdır.

Sözcüklerin birleştirilmesi: a = a₁a₂… a_n ve b = b₁b₂… b_m gibi iki sözcüğümüz varsa, bunların birleştirilmesiyle ab = a₁a₂… a_nb₁b₂… b_m sözcüğü oluşur. Örnek: “merhaba” ve “kedi” sözcüklerinin birleştirilmesiyle “merhabakedi” sözcüğü oluşur. Birleştirmeyi ya küçük bir halkayla, yani a ∘ b biçiminde gösteririz ya da hiçbir işaret koymadan sözcükleri art arda yazarız.

Boş sözcük ε ile gösterilir ve uzunluğu sıfır olan sözcük demektir. a = a₁… a_n sözcüğünü boş sözcük ε ile birleştirirsek yine a sözcüğünü elde ederiz. Yani a ∘ ε = a geçerlidir.

Σ alfabesinin Kleene kapanışı, Σ alfabesinden oluşturabildiğimiz, boş sözcük dâhil tüm sözcüklerin kümesidir. Kapanışı Σ^∗ ile gösteririz. İkili alfabe Σ= {0, 1} için şu geçerlidir:

$${\mathrm{\Sigma }}^{\ast }=\{\epsilon ,0,1,00,01,10,11,000,001,\dots \}$$

Bazen alfabenin pozitif kapanışını da kullanırız; bu, alfabeden kurabildiğimiz, boş sözcük dışındaki tüm sözcüklerdir. Pozitif kapanışı Σ⁺ ile gösteririz ve Σ⁺ = Σ^∗ ∖ {ε} olur.

Alfabe Örnekleri

• Türkçe örneğine geri dönelim. Her Türkçe sözcük, küçük ve büyük harfleri ve özel harfli biçimleri içeren (belki bir de tire “-” işaretini ekleyebileceğimiz) alfabenin kapanışında bulunur. Bu alfabeye boşluk ve noktalama işaretlerini (virgül, nokta, ünlem, soru işareti, …) de eklersek, kapanışta Türkçede kurabildiğimiz tüm cümleleri elde ederiz. Elbette bu kapanışta “sadflsf kasdf kagrjewişiağüçöışker kf fkjbsjbgvbadfgsa!!!:??: ::!?:?:sdf” gibi cümleler de bulunur.

• Alfabemiz tüm rakamları içeriyorsa, yani Σ= {0, 1, …, 9} ise, kapanışta tüm pozitif tam sayılar bulunur; ama fazladan başka sözcükler de vardır. Örneğin 00054 gibi sıfırla başlayan sayılar, tek başına 0 ve ayrıca hiçbir sayı olmayan boş sözcük de kapanışın içindedir.

• Alfabe boş olmamalıdır, yani en küçük alfabede en az bir sembol vardır. Örneğin Σ= {!} alfabesi için Σ^∗ = {ε, !, !!, !!!, !!!!, …} kapanışını elde ederiz. Bu, sözcüklerden oluşan bir kümedir; her n ∈ ℕ için kapanışta n tane ünlem içeren bir sözcük vardır ve kapanışta başka sözcük yoktur.

• Σ= {qw,c} olsun. Bu çok tuhaf bir alfabedir, çünkü qw sözcüğünü içerir. Bu gösterim genellikle kullanılmaz, çünkü kafa karıştırıcı ve gariptir; ama “q” ve “w” harflerinin birbirine yapışıp tek bir karakter oluşturduğunu düşünebiliriz. O zaman “qw” sözcüğünü “qw” sembolü olarak görebiliriz. Bu sembolden “qwcqw” sözcüğünü oluştursaydık, bu sözcüğün uzunluğu üç olurdu: “qw”, “c” ve “qw” sembollerinden oluşurdu. Bu tür alfabelerle pek sık karşılaşmayız, ama birden çok sembolden oluşan böyle sembolleri kullanmamız gereken durumlar vardır.

Biçimsel Dil

Σ alfabesi üzerinde (biçimsel) dil, Σ^∗ kümesinin herhangi bir alt kümesidir. Yani Σ alfabesi üzerindeki bir L dili için L ⊆ Σ^∗ geçerlidir. Dil örnekleri:

• Önceki bölümde Σ= {0, 1, …, 9} rakam alfabesini tanımlamıştık. Kapanışta yalnızca rakamlardan oluşan tüm sözcükler bulunur. Sözcüğün sıfırla başlayamayacağı ve boş olamayacağı kuralını eklersek pozitif tam sayılar kümesi ℤ⁺ elde edilir. ℤ⁺ ⊆ Σ^∗ bağıntısı geçerlidir, dolayısıyla ℤ⁺, Σ alfabesi üzerinde bir dildir.

• Önceki rakam kümesine eksi karakterini “-” de ekleyebiliriz, yani Σ= {0, 1, …, 9, −}. Kapanışta rakamlardan ya da eksi işaretinden oluşan tüm sözcükler bulunur. Bu da kapanışta “12-84-”, “1-5-8” ya da “-” gibi sözcüklerin bulunduğu anlamına gelir. Tam sayılar dilini ℤ, üç kural ekleyerek oluştururuz:

  • Eksi karakteri sözcükte hiç bulunmaz ya da sözcüğün başında bulunur.
  • “0” sözcüğü dışında, sözcükteki ilk rakam sıfır olamaz.
  • Her sözcük en az bir rakam içermelidir.

  Bu küme tam sayılar kümesini anlatır ve Σ^∗ kümesinin bir alt kümesidir — yani Σ alfabesi üzerinde bir dildir.

• Σ= {0, 1} olsun. Kapanışta sıfırlardan ve birlerden oluşan tüm sözcükler bulunur. Bu alfabe üzerinde L dilini örneğin tam olarak üç tane 1 içeren tüm sözcüklerin kümesi olarak tanımlayabiliriz. Daha yaratıcı da olabiliriz: L dili, geçerli bir docx dosya biçimini (Word’ün ürettiği şeyi) oluşturan tüm sözcüklerin kümesi olsun.

• İkili alfabe Σ= {0, 1} ile devam edelim. Klavyedeki her karakter dizisi, örneğin ASCII tablosu yardımıyla ikili biçime, yani sıfırlara ve birlere, ve tekrar geriye dönüştürülebilir (daha doğrusu ASCII tablosu karakterleri sayılara çevirir ve onluk tabandaki sayılar ikilik tabana çevrilebilir). Böylece geçerli bir e-postaya karşılık gelen tüm sözcüklerin dilini tanımlayabiliriz ve bu yine ikili alfabe üzerinde bir dil olur.

Dillerin birleştirilmesi: Dilleri de birleştirebiliriz. Tanım, kümelerin kartezyen çarpımına benzer. İki dil L₁ ve L₂ verilsin. Bunların birleştirilmesiyle L₁ ∘ L₂ yeni dilini elde ederiz ve şöyle tanımlarız:

$$L_1\circ L_2=\{w_1\circ w_2\mid w_1\in L_1,w_2\in L_2\}$$

Yani L₁ dilindeki tüm sözcükleri alır ve L₂ dilindeki tüm sözcüklerle birleştiririz. Örnek:

$$\begin{array}{rcl}{L}_1& =& \{0,1\}\\ L_2& =& \{a,b,merhaba\}\end{array}$$

olsun. O zaman:

$$\begin{array}{rcl}{L}_1\circ L_2& =& \{0a,0b,0merhaba,1a,1b,1merhaba\}\\ L_2\circ L_1& =& \{a0,a1,b0,b1,merhaba0,merhaba1\}\\ L_1\circ L_1& =& \{00,01,10,11\}\end{array}$$

Şimdiye kadar dilleri anlatmak için sıradan bir dil kullandık, yani dilin nasıl görünmesi gerektiğini sözle anlattık. Ama bu çok pratik değildir, bu yüzden bir dili tanımlamak için daha biçimsel yollar geliştirilmiştir. Bunlardan ilki gramerdir.