Derivation process, yani türev süreci, formal dil teorisinde ve özellikle konteksten bağımsız gramerlerde, bir başlangıç sembolünden (genellikle başlangıç nonterminali) başlayarak belirli üretim kurallarını adım adım uygulayarak bir dilin çıktılarını (kelimeleri veya cümleleri) üretme metodudur. Bu süreç, belirlenen gramer kurallarına göre stringleri (kelime dizilerini) nasıl oluşturduğunu gösterir ve dilin yapısal özelliklerini anlamak için temel bir araçtır.

Türev Sürecinin Temel Adımları

Başlangıç: Türev süreci, gramerin başlangıç sembolü ile başlar. Bu sembol genellikle S ile gösterilir ve dilin üretimine başlamak için kullanılır.

Uygulama: Üretim kuralları, belirli bir nonterminalin nasıl bir veya daha fazla nonterminal ve terminal sembol dizisine dönüştürülebileceğini belirtir. Türev sürecinde, bu kurallar sırasıyla uygulanarak başlangıç sembolü gittikçe daha karmaşık stringlere dönüşür.

Genişleme: Her adımda, türevlenecek sembollerden (nonterminaller) biri seçilir ve bu sembol için uygun olan üretim kuralı uygulanır. Bu işlem, türevlenecek başka nonterminal kalmayana kadar devam eder.

Sonlanma: Türev süreci, üretilen stringde nonterminal sembol kalmadığında tamamlanır. Sonuçta elde edilen string, gramer tarafından üretilen bir dil örneğidir.

Türev Türleri

Sol Türev: Her adımda stringin sol tarafındaki ilk nonterminal, uygun bir üretim kuralı ile değiştirilir.

Sağ Türev: Her adımda stringin sağ tarafındaki son nonterminal, uygun bir üretim kuralı ile değiştirilir.

Örnek

Bir gramer G şu şekilde tanımlansın:

S→AB

A→a

B→b

Başlangıç sembolü S ile başlayarak "ab" stringinin sol türevi:

S→AB

AB→aB (sol türevde ilk nonterminal olan A değiştirilir)

aB→ab (son nonterminal B değiştirilir)

Türev süreci, dilbilimindeki yapıların nasıl oluşturulduğunu anlamak ve derleyici gibi dil işlemeyi gerektiren yazılımların nasıl çalıştığını kavramak için kritik öneme sahiptir. Bu süreç aynı zamanda dilin yapısını ve dil kurallarını öğretmede temel bir yöntemdir.

def apply_rule(symbol, rules):
    # Eğer sembol için bir kural varsa, ilk uygun kuralı uygula
    if symbol in rules:
        return rules[symbol]
    else:
        return symbol

def derive(start_symbol, rules, max_steps=10):
    # Türev başlangıcı
    output = start_symbol
    print("Başlangıç:", output)
    
    # Türev adımlarını gerçekleştir
    for _ in range(max_steps):
        new_output = ""
        expanded = False
        
        # Çıktıdaki her sembol için
        for symbol in output:
            # Kural uygula
            result = apply_rule(symbol, rules)
            new_output += result
            # Eğer türev genişletildi ise, işaretle
            if result != symbol:
                expanded = True
        
        output = new_output
        print("Türev adımı:", output)
        
        # Eğer tüm semboller terminaller ise, döngüyü bitir
        if not expanded:
            break

# Gramer kuralları
rules = {
    'S': 'AB',
    'A': 'a',
    'B': 'b'
}

# Türev sürecini başlat
derive('S', rules)

Çıktı:

Başlangıç: S
Türev adımı: AB
Türev adımı: ab
Türev adımı: ab