Transduced-Input Finite Automata with Translucent Letters

Abstract

Finite automata with translucent letters are extensions of the usual finite state automata allowing to proceed the input not strictly left to right manner. There are some letters which are translucent for each internal state such that the automaton cannot read them. These are finite state devices that are able to accept a class of languages that is a superset of the regular languages, moreover, it contains some non-context-free languages. The class is closed under union, concatenation, however, it is not closed under intersection with regular sets. There are three linguistically important non context-free languages: the multiple agreement, the cross dependencies and the marked copy. These languages cannot be accepted by finite automata with translucent letters. In this thesis an extension of the model is presented in which the input is preprocessed by a finite state transducer. The transduced input is given to the finite automata with translucent letters, and it decides on acceptance. This is named as T-inputFAwtl i.e. Transduced-Input Finite Automata with Translucent Letters. We prove that all the three mentioned languages are accepted by the deterministic variant of the new model i.e. T-inputDFAwtl. Because of this we say that T-inputFAwtl has more expressive power than original finite automata with translucent letters. We also presented some closure properties of the class of languages accepted by non deterministic variant of this model i.e. T-inputNFAwtl. We proved that the language class accepted by that T inputNFAwtl is closed under union (if the same transducer is used), and it is closed under intersection with regular languages. Keywords: t-input automata, automata with translucent letters, Mealy automata, formal languages, finite state machines, transducers, finite state machines, closure properties

ÖZ: Yarı saydam harflere sahip sonlu otomatlar, girişin kesinlikle sağdan sola doğru ilerlememesine izin veren olağan sonlu durum otomatının uzantılarıdır. Her iç durum için yarı saydam olan bazı harfler vardır, böylece otomat onları okuyamaz. Bunlar, normal dillerin bir üst kümesi olan bir dil sınıfını kabul edebilen sonlu durum aygıtlarıdır, ayrıca bazı bağlamsız diller içerir. Sınıf birleşme, yan yana koyma işlemleri altında kapalıdır, ancak düzenli kümelerle kesişme işlemi altında kapalı değildir. Dilsel açıdan önemli üç bağlamsız dil vardır: çoklu anlaşma, çapraz bağımlılıklar ve işaretli kopya. Bu diller yarı saydam harfli sonlu otomatlar tarafından kabul edilemez. Bu tezde, girdinin sonlu durum transdüseri tarafından önceden işlendiği modelin bir uzantısı sunulmaktadır. Dönüştürülen giriş yarı saydam harfli sonlu otomata verilir ve kabul etmeye karar verir. Buna T-inputFAwtl, yani Translucent Letters ile Transduced-Input Sonlu Otomata denir. Bahsedilen üç dilin hepsinin yeni modelin deterministik değişkeni, yani T-inputDFAwtl tarafından kabul edildiğini kanıtlıyoruz. Bu nedenle T-inputFAwtl'ın yarı saydam harflerle orijinal sonlu otomattan daha etkileyici bir güce sahip olduğunu söylüyoruz. Bu modelin deterministik olmayan değişken tarafından kabul edilen dil sınıfının bazı kapatma özelliklerini yani T inputNFAwtl de tezde sunduk, T-inputNFAwtl tarafından kabul edilen dil sınıfının birleşim altında (aynı dönüştürücü kullanılıyorsa) ve normal dillerle kesişme işlemleri altında kapalı olduğunu kanıtladık. Anahtar Kelimeler: t-girdi otomatları, yarı saydam harfli otomatlar, Mealy otomatları, biçimsel diller, sonlu durum makineleri, dönüştürücüler, sonlu durum makineleri, kapalılık özellikleri