Ω-Αναγνωρισιμότητα λέξεων:
Creators: name: Ντεμηρούδη, Σωτηρία Αντωνίου
Publisher: name: Aristotle University of Thessaloniki
Year: 2011
Subjects: Άπειρες λέξεις
Αυτόματα Buechi και Muller
Αναγνωρίσιμες γλώσσες
Infinite words
Buechi and Muller automata
Recognizable languages

description: Στο πρώτο κεφάλαιο εισάγονται έννοιες και χαρακτηριστικά των πλήρη αυτομάτων και στοιχεία που αφορούν τον σχεδιασμό τους. Ακολουθεί ορισμός των αναγνωρίσιμων γλωσσών των αυτομάτων και αποδεικνύονται βασικές προτάσεις οι οποίες ισχύουν γι’ αυτές. Το κεφάλαιο ολοκληρώνεται με την κατηγοριοποίηση των αυτομάτων ανάλογα με τη γλώσσα που αναγνωρίζει καθένα από αυτά. Στη συνέχεια, το επόμενο κεφάλαιο αναφέρεται στα αυτόματα που επεξεργάζονται άπειρες γλώσσες και είναι γνωστά ως Büchi αυτόματα. Στο δεύτερο κεφάλαιο έχουμε τη δυνατότητα να συναντήσουμε ορισμούς, έννοιες και θεωρήματα που περιγράφουν αυτή την κατηγορία αυτομάτων καθώς και τις γλώσσες που αναγνωρίζονται από αυτά. Το τρίτο κεφάλαιο είναι εξ’ ολοκλήρου αφιερωμένο στην αναλυτική απόδειξη των δύο θεωρημάτων Büchi μέσα από τα οποία παρατίθενται οι ικανές και αναγκαίες συνθήκες που απαιτούνται ώστε να είναι μία γλώσσα Büchi αναγνωρίσιμη. Στο τέταρτο κεφάλαιο μελετάμε το πρόβλημα της συμπληρωματικότητας των Büchi αυτομάτων. Με άλλα λόγια τιθέμεθα να απαντήσουμε στο σημαντικό ερώτημα του αν υπάρχει Büchi αυτόματο που να αναγνωρίζει όλες εκείνες τις -λέξεις που δεν είναι αναγνωρίσιμες από ένα άλλο αυτόματο του είδους. Εφόσον περιγράψουμε αναλυτικά τα στοιχεία του προβλήματος της συμπληρωματικότητας των Büchi αυτομάτων, ακολουθεί απόδειξη του θεωρήματος της συμπληρωματικότητας των απείρων αυτών αυτομάτων. Στο επόμενο κεφάλαιο παρουσιάζεται μια εξίσου σημαντική κατηγορία αυτομάτων, τα λεγόμενα Muller αυτόματα (ντετερμινιστικά πεπερασμένα αυτόματα που ακολουθούν άπειρες διαδρομές). Τα Muller αυτόματα παρουσιάζουν ομοιότητες αλλά και διαφορές σε σύγκριση με τα ντετερμινιστικά Büchi αυτόματα, τις οποίες καλούμαστε να αναλύσουμε στο πέμπτο αυτό κεφάλαιο. Στη συνέχεια ακολουθούν δυο βασικά θεωρήματα, όπου το πρώτο αναφέρεται σε στοιχειώδεις ιδιότητες των Muller αναγνωρίσιμων γλωσσών ενώ το δεύτερο θεώρημα αποτελεί το χαρακτηριστικό θεώρημα μίας Muller αναγνωρίσιμης γλώσσας. Επιλογικά, η εργασία ολοκληρώνεται με το έκτο κεφάλαιο στο οποίο επιχειρούμε να δώσουμε ένα παράδειγμα μίας Büchi αναγνωρίσιμης γλώσσας που δεν μπορεί να αναγνωριστεί από τα ντετερμινιστικά Büchi αυτόματα. Μέσα από το παράδειγμα αυτό, αποδεικνύουμε ότι το σύνολο των -γλωσσών που είναι Büchi αναγνωρίσιμες δεν είναι κλειστό ως προς την συμπληρωματικότητα τους, γεγονός που οδήγησε στο να οριστεί την άλλη κατηγορία αυτομάτων, τα ντετερμινιστικά Μuller αυτόματα.
description: The first chapter introduces concepts and features of full automatic and information relating to their design. Here is the definition of recognizable languages of automata and prove key recommendations which apply to them. The chapter concludes with automatic categorization according to language that recognizes each of them. Then, the next chapter refers to automatic processing countless languages and are known as Büchi automatically. In the second chapter we can find definitions, concepts and theorems that describe this class of automata and languages recognized by them. The third chapter is entirely devoted to a detailed proof of two theorems Büchi through which gives the necessary and sufficient conditions required to be a language Büchi recognizable. In the fourth chapter we study the problem of complementarity of Büchi automata. In other words tithemetha to answer the important question of whether there Büchi automatically recognizing all those-words that are not identifiable by another type of automatic. Since describe in detail the elements of the problem of complementarity of Büchi automata, following proof of the theorem of complementarity of these infinite automata. The next chapter presents an equally important category of automata, called Muller automatically (deterministic finite automata that follow infinite paths). The Muller automatically show similarities and differences compared with the deterministic Büchi automatically, which we analyze in this fifth chapter. Then follow two main theorems, where the first refers to basic properties of Muller recognizable languages while the second theorem is a theorem feature Muller recognizable language. Option, the task is completed with the sixth chapter in which we attempt to give an example of a Büchi recognizable language can be recognized by deterministic Büchi automatically. Through this example, we prove that all languages- Büchi recognizable is not closed in terms of their complementarity, which led to the other designated group automata, the deterministic Muller automatically.