Παραγωγή Αναγνωρίσιμων Γλωσσών με Μοντέλα Ανασυνδυασμού Αλυσίδων DNA
Creators: name: Γίδαρη, Λαμπρινή Κωνσταντίνου
Publisher: name: Aristotle University of Thessaloniki
Year: 2015
Subjects: Συντακτικό μονοειδές
Splicing συστήματα
Αναγνωρίσιμη γλώσσα
Syntactic monoid
Splicing systems
Regular language

description: Στην παρούσα διπλωματική εργασία ασχολούμαστε με την παραγωγή αναγνωρίσιμων γλωσσών με μοντέλα ανασυνδυασμού DNA. Συγκεκριμένα, θα εξετάσουμε τα δύο είδη splicing συστημάτων, τα Pixton splicing συστήματα και τα κλασσικά splicing συστήματα. Θα ορίσουμε το splicing ως μια διαδικασία πάνω σε λέξεις, εμπνευσμένη από τον ανασυνδυασμό του DNA μέσω των περιοριστικών ενζύμων και της DNA λιγάσης. Την έννοια αυτή την εισήγαγε ο Tom Head το 1987. Στο πρώτο κεφάλαιο θα παρουσιάσουμε τη δομή του DNA και τις βιολειτουργίες του επικεντρώνοντας την προσοχή μας στην splicing διαδικασία. Έπειτα θα θέσουμε το μαθηματικό υπόβαθρο το οποίο θα μας βοηθήσει να ανακαλέσουμε στη μνήμη μας κάποιες βασικές έννοιες από τη Θεωρία Τυπικών Γλωσσών και επιπλέον θα παραθέσουμε δύο βασικά Λήμματα που αφορούν τα συντακτικά μονοειδή των αναγνωρίσιμων γλωσσών. Τέλος θα αποδείξουμε μια pumping τεχνική η οποία είναι σημαντική για την απόδειξη των αποτελεσμάτων στη συνέχεια. Στο δεύτερο κεφάλαιο θα μιλήσουμε για τα splicing συστήματα και θα αναλύσουμε αντίστοιχα και τις δύο περιπτώσεις αυτών: Pixton splicing συστήματα και κλασσικά splicing συστήματα. Σε κάθε μία από αυτές τις περιπτώσεις θα δείξουμε με ποιον τρόπο μπορούμε να τροποποιήσουμε τους splicing κανόνες τηρώντας συγκεκριμένα όρια με σκοπό να δείξουμε ότι μια αναγνωρίσιμη γλώσσα προέρχεται από ένα splicing σύστημα. Στο τελευταίο κεφάλαιο ασχολούμαστε με το θέμα της αποφασισιμότητας θέτοντας το ερώτημα αν μια δοσμένη αναγνωρίσιμη γλώσσα μπορεί να παραχθεί από ένα splicing σύστημα.
description: In the current master thesis we are dealing with the generation of regular languages using recombinant DNA models. We will particularly investigate two specific splicing systems namely, Pixton splicing systems and classic splicing systems. We will define the splicing operation as a procedure based on words inspired by the recombination of the DNA molecule via restriction enzymes and DNA ligase. This term was introduced by Tom Head, in 1987. In the first chapter we will cite the structure of DNA molecule and its biological functions, concentrating especially upon the splicing procedure. Afterwards, we will set the mathematical framework, which will help us recall the basic principles of the Formal Language Theory. In addition to this, we will point to two basic Lemmas that refer to syntactic monoids of regular languages. Finally, we will support a pumping argument that is very important for the proof of our results in the sequel. In the second chapter we are going to talk about splicing systems and analyze both cases: Pixton splicing systems and classic splicing systems. In each case, we are going to point out the way through which the splicing rules can be modified, abiding by specific limits, with the aim of proving that a recognizable language descents from a splicing system. In the last chapter, we are dealing with the issue of decidability by setting the question whether a given regular language can be obtained from a splicing system or not.