Biçimsel Diller ve Soyut Makineler – 2 – Diller ve Katar ( String ) İşlemleri

Biçimsel Diller ve Soyut Makineler

Diller

Dil: Karakter katarları kümesidir. Örneğin bizim bir alfabemiz olsun. Bu alfabe de sadece “c”  ve “d” harfleri bulunsun. Katar yani String bu alfabe üzerine kurulu, tanımlı Karakter (letter) dizisidir.

Σ = { a,b,c,d, ….., z}

Örnek olarak  : “ali”, “veli”, “deli” verilebilir.

Bir başka örnek verecek olursak;

Σ = {a,b,c}

Strings ( Katarlarımız )

a

ab

abc

abca

cab

String İşlemleri

w = abc

v = ba

wv = abcba

w^R = cba

|w| =3

|wv| = |w| + |v|

5 = 3 + 2

Boş String Kavramı ( λ )

|λ| = 0

λw = wλ = w

λabba = abbaλ = abba

Alt Katar Kavramı (Substring)

abbabaa = ab, a, abba, aa , ba (bunların hepsi substring e örnek olabilir)

Prefix, Suffix Kavramı

abbabaa = ab(prefix), babaa(suffix) olabilir.

Üs işlemi

w = ababb

wⁿ = n tane w nin çarpımı( Eğer n 0’a eşit değil ise )

w⁰ = λ

w² = ababbababb

Kleene (*) İşlemi

Σ = { x, y }

∑* = { λ, x, y, xx, yy, xyyy, yxxxx, yxxy, ……. } sonsuza kadar gidebilir.

Plus ( ⁺ )  İşlemi

Σ = { x, y }

∑⁺ = { x, y, xx, yy, xyyy, yxxxx, yxxy, ……. } sonsuza kadar gidebilir.