Otomata Teorisi I (Automata Theory I)

Otomata 'kendi kendine hareket eden' anlamına gelen Yunanca "αὐτόματα" kelimesinden türetilmiştir. Bir otomata otomatik olarak operasyonları önceden belirlenmiş bir sıra ile izleyen soyut işlem aygıtıdır.

Stringler, Alfabe (Character Set) ve Diller (Languages)

Alfabe (Character Set): Sonlu sayıda sembol içeren kümeye denir.
{0,1} : ikili alfabe

String: Bir alfabe üzerinde tanımlı string, bu alfabenin sonlu sayıdaki sembolün bir araya gelmesinden
oluşur. String s’nin uzunluğu |s| olarak gösterilir ve s içerisinde bulunan karakterlerin sayısı olarak
tanımlanır. Boş (empty) string ε ile gösterilir ve uzunluğu 0’dır.
|burak|= 5

Dil (Language): Verilen alfabe üzerinde tanımlı stringlerin kümesini oluşturur.

Ø: boş küme

{ ε }: (sadece boş string içeren küme)

String İşlemleri

Birleştirme (Concatenation): x ve y iki string olsun. x ve y üzerine birleştirme işlemi uygulandığında xy olarak gösterilir ve y’nin x’e eklenmesi sonucu elde edilir.

x = dog ve y = house ise xy = doghouse

s ε = ε s = s
ε birleştirme işlemi altında birim elemandır.

Birleştirme işlemi bir çarpım işlemi olarak düşünülebilir, dolayısıyla stringler üslü olarak tanımlanabilir.

s⁰ = ε , s¹= s, s²= ss, s³= sss

Prefix: String’in sonundan sıfır veya daha fazla sayıda sembol çıkararak elde edilen yeni stringe asıl stringin prefixi denir.

bu, burak stringinin bir prefixidir.

Suffix: String’in başından sıfır veya daha fazla sayıda sembol çıkararak elde edilen yeni stringe asıl stringin suffixi denir.

ak, burak stringinin bir suffixidir.

Substring: Stringin herhangi üzerine prefix ve suffix ile sıfır veya daha fazla sayıda sembol çıkararak elde edilen stringe asıl stringin substringi denir.

r, burak stringinin bir substringidir.

Herhangi bir string s icin, s ve ε hem prefix, hem suffix ve hemde substringdir.

Subsequence: Sıfır veya daha fazla sembolün çıkarılmasıyla (çıkarılan semboller ardışık olmak zorunda değil) elde edilir.

brk, burak stringinin bir subsequencidir.

L bir olmak üzere:

L⁰= { ε }

Lⁱ= L^i-1L

L ve D iki tanımlı dildir.

L = {A,B,…,Z,a,b,…,z}
D = {0,1,…, 9}

Union: LUD={s|s L’nin elemanı veya D’nin elemanı}

LUD: Harflerden ve rakamlardan oluşan küme

Concatenation: LD={st| s L’nin elemanı ve t D’nin elemanı)

LD: Başı harf sonu rakam olan stringlerin kümesi

Düzenli İfadeler (Regular Expression)

Σ bir alfabe olmak üzere:

1. Bir düzenli ifade olarak { ε }’yi ifade eder.

2. Eğer a Σ alfabesinin bir elemanı ise a bir düzenli ifadedir ve {a}’yi tanımlar.

3. Eğer r ve s iki düzenli ifadeleri ve L(r) ve L(s) tanımlıyorsa:

( r ) | ( s ), L( r ) U L( s )’ i ifade eden bir düzenli ifadedir.

( r )( s ), L( r )L( s )’ i ifade eden bir düzenli ifadedir.

( r )*, ( L( r ) )*’ i ifade eden bir düzenli ifadedir.

( r ), L( r )’yi ifade eden bir düzenli ifadedir.

Düzenli İfade Öncelikleri (Regular Expression Precedence)
1. * tekli (unary) operatör olarak en yüksek önceliğe sahiptir.
2. Concatenation (birleştirme) 2. en yüksek önceliğe sahiptir.
3. Union ise en düşük önceliğe sahiptir.

Düzenli İfade Özellikleri (Regular Expression Properties)

1. r|s = s|r (değişme özelliği)

2. r( s|t ) = rs|rt (dağılma özelliği)

3. ( s|t )r = sr|tr (dağılma özellliği)

4. ε r = r ε = r (ε: birim eleman)
5. r* = ( r |ε )*

6. r**= r*

Düzenli İfadelerle Tanımlı Değişkenler (Varibles)

letter → A | B |…| Z | a | b |…| z

digit → 0 | 1 |…| 9

id → letter( letter| digit)*

Düzenli İfadelerle Tanımlı İşaretsiz Sayılar (Unsigned Numbers)

digit → 0 | 1 |…|9

digits → digit digit*

optional_fraction → .digits | ε

optional_exponent → (E (+ | - | ε) digits ) | ε

num → digits optional_fraction optional_exponent

Ek Düzenli İfade Tanımları ile İşaretsiz Sayılar (Unsigned Numbers)

(r)⁺= {L(r)⁺}

(r)? = L(r) U { ε }
[0-9] = 0 | 1 |...|9

digit → [0-9]

digits → digit+

optional_fraction → (. digits)?

optional_exponent → (E (+ | -)?digits )?

num → digits optional_fraction optional_exponent

Regular Expressions	Regular Set
(0 \|10^*)	L= { 0, 1, 10, 100, 1000, 10000, … }
(0^10^)	L={ 1, 01, 10, 010, 0010, … }
(0 \| ε)(1 \| ε)	L= { ε, 0, 1, 01 }
(a \| b)^*	L= { ε, a, b, ab , ba, aab, bba, … }
(a \| b)*abb	a ve b’lerden oluşan ve aab stringi ile sonlanan dil, L = {abb, aabb, babb, aaabb, ababb, … }
(11)^*	Çift sayıda 1’den oluşan dil, L= { ε, 11, 1111, 111111, … }
(aa)(bb)b	Çift sayıda a ve tek sayıda b’lerden oluşan dil, L= { b, aab, aabbb, aabbbbb, aaaab, aaaabbb, … }
(aa + ab + ba + bb)^*	L= {aa, ab, ba, bb, aaab, aaba, … }