Güçlendirilmiş sonlu durumlu makine modelleri

Literatürde ortaya sürülmüş olan pek çok makine, bir sonlu durumlu makinenin ek bir hafıza ünitesi ile güçlendirilmiş hali olarak düşünülebilir. Bu tezde, bu makine-\newline lerden ikisine, gruplar üzerinde tanımlı sonlu durumlu makinelere ve eve dönen vektör makinelerine odaklanılmıştır. $ G $ grubu üzerinde tanımlı bir makine, sahip olduğu ek hafıza ünitesinde $ G $ grubundan bir elemanı tutma hakkına sahip, belirlenimci olmayan bir sonlu durumlu makinedir. Başlangıçta hafıza ünitesinin değeri $ G $ grubunun birim elemanıdır. Bir hesaplamanın başarılı sayılabilmesi için hafıza ünitesinin değerinin, her adımda grubun bir elemanıyla çarpıldıktan sonra bitimde grubun birim elemanına eşit olması beklenir. Bu çalışmada tam sayılı ve rasyonel sayılı matris grupları üzerinde tanımlanan sonlu durumlu makine-\newline ler incelenmiş, bu makinelerin tanıdığı dil sınıflarının birbirleri ile olan ilişkileri ortaya çıkarılmıştır. Grubun büyüme hızı, makinelerin çalışma süresi gibi çeşitli parametrelere bakılarak, bu parametrelerin makinelerin tanıma gücünü nasıl etkilediği araştırılmıştır. Matris yarıgruplarının karar verme problemleri ile ilintili makinelerin karar verme problemleri arasında bir bağ kurulmuştur. Grup üzerinde tanımlı makinelerle yakından ilişkili olan bazı modeller incelenmiş ve bir takım yeni sonuçlar elde edilmiştir. Yeni tanımladığımız eve dönen vektör makinesi, bir sonlu durumlu makinenin bir vektörle güçlendirilmesi ve makineye bu vektörü her adımda bir matrisle çarpma hakkı verilmesiyle ortaya çıkmıştır. Makinenin vektörün başlangıç vektörüne eşit olup olmadığını kontrol etme hakkı vardır ve makinenin kabul şartı, hesaplama bittiğinde vektörün başlangıç vektörüne eşit olması ve kabul durumlarından birinde bulunulmasıdır. Kullanılan matris kümesi sınırlanarak ve vektörün eşitlik kontrolünün sadece en sonda gerçekleşmesine izin verilerek, farklı kısıtlamaların makineye olan etkisi incelenmiştir. Makinenin çeşitli sürümleri tanımlanarak, bu modellerin dil tanıma gücüyle klasik modellerin dil tanıma gücü karşılaştırılmıştır. Matris grupları üzerinde tanımlı sonlu durumlu makinelerle, bir yönlü belirlenimci olmayan kör eve dönen vektör maki-\newline neleri arasında ilişki kurularak eve dönen vektör makineleri ile ilgili yeni sonuçlar elde edilmiştir. Gerçek zamanlı eve dönen vektör makineleri üzerinde özellikle durulmuş, bazı kapalılık özellikleri gösterilmiş ve bu makinelerin tek durumlu versiyonları analiz edilmiştir. Stern-Brocot ağacından faydalanarak dizgeleri vektörlere kodlamaya yarayan bir metod geliştirilmiştir.