Development of an educational graphical tool for finite state machine simulationDevelopment of an educational graphical tool for finite state machine simulationΑνάπτυξη εκπαιδευτικού γραφικού εργαλείου προσομοίωσης πεπερασμένων αυτομάτων Διπλωματική Εργασία 2014-03-242013enAutomata (also known as state machines) are abstract mathematical models used widely in theoretical computer science for the study of computability, but also in several practical applications. In the literature, they are oftentimes depicted as directed graphs. Their graphical representation makes automata an ideal intuitive way of communicating fundamental concepts of the Theory of Computation. Many academic institutions use educational software tools that simulate automata in an interactive way to facilitate the teaching process. This thesis describes our approach to creating such a software tool, called FA-Sim, which is a graphical interactive simulator for the most basic type of automata, called Finite Automata or Finite State Machines. Our tool is consistent with and customized for the course of Theory of Computation taught at our institution. The user (student or instructor) is able to graphically create, edit, and simulate any deterministic or nondeterministic finite automaton on any given input and observe the resulting computation step-by-step. Additionally, our tool features automatic conversion from any nondeterministic finite automaton to an equivalent deterministic one. Finally, our tool supports import of automata specified in the text-based JSON open standard and export of any automaton's graphical representation to several image file formats. Our implementation is based entirely on the Java programming language, following the principles of object-oriented programming. The graphical user interface was developed using Swing, the native Java library for user interfaces, and JUNG, a third-party Java framework for manipulating graphs. The internal representation of automata for the purposes of storage and retrieval is based on GraphML, an XML-based file format for graphs. The user evaluations we conducted with students from the Theory of Computation class revealed several user interface suggestions and preferences, which were taken into account and incorporated into the latest version of FA-Sim. All student participants agreed that FA-Sim would indeed be a useful tool in the better understanding of the concept of finite automata. Τα αυτόματα (επίσης γνωστά και ως μηχανές καταστάσεων) είναι αφηρημένα μαθηματικά μοντέλα που χρησιμοποιούνται ευρέως στη θεωρητική επιστήμη των υπολογιστών για τη μελέτη της υπολογισιμότητας, αλλά και σε πολλές πρακτικές εφαρμογές. Στη βιβλιογραφία, συνήθως απεικονίζονται ως κατευθυνόμενοι γράφοι. Η γραφική τους αναπαράσταση τα καθιστά ένα ιδανικό διαισθητικό τρόπο μετάδοσης θεμελιωδών εννοιών της Θεωρίας Υπολογισμού. Πολλά ακαδημαϊκά ιδρύματα χρησιμοποιούν εκπαιδευτικά εργαλεία λογισμικού που προσομοιώνουν αυτόματα με διαδραστικό τρόπο προς διευκόλυνση της εκπαιδευτικής διαδικασίας. Η παρούσα διπλωματική εργασία περιγράφει την δική μας προσέγγιση για τη δημιουργία ενός τέτοιου εργαλείου λογισμικού, που ονομάσαμε FA-Sim, και αποτελεί έναν γραφικό διαδραστικό προσομοιωτή για το πιο βασικό είδος αυτομάτων, τα πεπερασμένα αυτόματα ή μηχανές πεπερασμένων καταστάσεων. Το εργαλείο μας είναι συνεπές με το μάθημα της Θεωρίας Υπολογισμού που διδάσκεται στο ίδρυμά μας και προσαρμοσμένο στις ανάγκες του. Ο χρήστης (μαθητής ή διδάσκων) είναι σε θέση να δημιουργήσει, να επεξεργαστεί και να προσομοιώσει γραφικά οποιοδήποτε ντετερμινιστικό ή μη ντετερμινιστικό πεπερασμένο αυτόματο σε οποιαδήποτε δεδομένη είσοδο και να παρατηρήσει τον υπολογισμό βήμα προς βήμα. Επιπλέον, το εργαλείο μας υποστηρίζει την αυτόματη μετατροπή από οποιοδήποτε μη ντετερμινιστικό πεπερασμένο αυτόματο σε ισοδύναμο ντετερμινιστικό. Τέλος, το εργαλείο μας υποστηρίζει την εισαγωγή αυτομάτων που περιγράφονται με το ανοικτό πρότυπο κειμένου JSON και την εξαγωγή της γραφικής αναπαράστασης οποιουδήποτε αυτομάτου σε διάφορες μορφές αρχείων εικόνας. Η υλοποίησή μας βασίζεται εξ ολοκλήρου στην γλώσσα προγραμματισμού Java και ακολουθεί τις αρχές του οντοκεντρικού προγραμματισμού. Το γραφικό περιβάλλον χρήστη αναπτύχθηκε χρησιμοποιώντας την βιβλιοθήκη Swing της Java για περιβάλλοντα χρήστη και το εργαλείο διαχείρισης γράφων JUNG. Η εσωτερική αναπαράσταση αυτομάτων για τις ανάγκες αποθήκευσης και ανάκτησης βασίζεται στο πρότυπο αρχείων για γραφήματα GraphML. Οι αξιολογήσεις των χρηστών που διεξήχθησαν με φοιτητές από την τάξη της Θεωρίας Υπολογισμού αποκάλυψαν αρκετές προτάσεις και προτιμήσεις σε θέματα διεπαφής χρήστη, οι οποίες ελήφθησαν υπόψη και ενσωματώθηκαν στην τελευταία έκδοση του FA-Sim. Όλοι οι συμμετέχοντες συμφώνησαν ότι το εργαλείο FA-Sim θα μπορούσε πράγματι να φανεί χρήσιμο για την βαθύτερη κατανόηση της έννοιας των πεπερασμένων αυτομάτων. http://creativecommons.org/licenses/by/4.0/Πολυτεχνείο Κρήτης::Σχολή Ηλεκτρονικών Μηχανικών και Μηχανικών ΥπολογιστώνKoukoubedakis_Georgios_Dip_2013.pdfChania [Greece]Library of TUC2022-05-06application/pdf2.3 MBfree Koukoubedakis Georgios Κουκουμπεδακης Γεωργιος Lagoudakis Michail Λαγουδακης Μιχαηλ Deligiannakis Antonios Δεληγιαννακης Αντωνιος Mania Aikaterini Μανια Αικατερινη Πολυτεχνείο Κρήτης ΔΙΠ3143