*DFA ile bir metnin sonunu kontrol etmek

DFA burada neyi hatırlıyor?

DFA, deterministic finite automaton'ın kısaltması. Türkçede deterministik sonlu otomat deniyor. “Sonlu” kısmı, makinenin sınırlı sayıda durumu olması. “Deterministik” kısmı ise bulunduğu durum ve sıradaki karakter belli olduğunda gideceği yerin de belli olması. Tablodaki her hücre tam olarak bunu söylüyor.

Bu örnekte yalnızca 0 ve 1 kabul ediyorum. S0, son karakterin bir olduğu veya henüz hiçbir şey okunmadığı durum. S1, son karakterin sıfır olduğunu söylüyor. S2 ise son iki karakterin 01 olduğunu hatırlıyor. Girdinin tamamını saklamama gerek yok.

Tabloda S2'den yeni bir 1 geldiğinde S0'a dönmemizin nedeni de bu. Örneğin 011 artık 01 ile bitmiyor. Yeni bir 0 gelirse S1'e geçiyoruz; çünkü bu sıfır, sonraki bir ile yeni bir 01 oluşturabilir.

Bir metnin 01 ile bitip bitmediğini kontrol etmek için son iki karaktere bakabiliriz. Aynı işi bir durum makinesiyle düşünmek de mümkün. Bu örnekte okumaya devam ederken neyi hatırlamamız gerektiğine bakıyorum.

Üç durum yeterli: henüz bir eşleşme yok, son okunan karakter 0, son okunan iki karakter 01. Bunlara sırasıyla S0, S1 ve S2 diyelim.

Okuma S0 ile başlıyor. 001 için önce S1'e geçiyoruz, ikinci sıfırda orada kalıyoruz, son birde S2'ye ulaşıyoruz. Girdi bittiğinde S2'deysek metin 01 ile bitiyor.

Metnin içinde aramak

Burada kontrol ettiğimiz şey metnin sonu. Metnin herhangi bir yerinde 01 geçmiş mi diye bakacaksak kabul durumuna ulaştığımız an durabiliriz. Daha uzun desenlerde ise eşleşme bozulduğunda hangi parçayı hatırlayacağımızı hesaplamak gerekiyor.

Örneğin abc desenini aabc içinde ararken ikinci a yeni bir başlangıç olabilir. Eşleşme bozulunca o karakteri de tüketip doğrudan sıfıra dönmek, bu eşleşmeyi kaçırır. Bir desen arayıcı yazarken asıl dikkat edeceğim yer bu geçişler.

JavaScript karşılığı

Tabloyu doğrudan kodda tutabiliyorum. Her karakterde mevcut durumun satırına bakıp bir sonraki durumu seçiyorum:

function endsWith01(input) {
  const transitions = {
    S0: { '0': 'S1', '1': 'S0' },
    S1: { '0': 'S1', '1': 'S2' },
    S2: { '0': 'S1', '1': 'S0' },
  };
  let state = 'S0';

  for (const char of input) {
    if (char !== '0' && char !== '1') {
      throw new Error('Girdi yalnızca 0 ve 1 içermeli');
    }
    state = transitions[state][char];
  }

  return state === 'S2';
}

console.log(endsWith01('001')); // true
console.log(endsWith01('011')); // false
console.log(endsWith01(''));    // false

Bu kadar küçük bir kontrolü gerçek bir projede input.endsWith('01') ile yazarım. Durum tablosu burada işlemin nasıl yürüdüğünü görmek için kullanışlı. Bir protokolü veya adım adım ilerleyen bir akışı modellediğimizde de aynı soruyu sorabiliriz: şu an hangi durumdayız ve bu girdi bizi nereye götürmeli?