Σχεδιασμός και υλοποίηση εφαρμογής με γραφικό περιβάλλον για μετατροπή NFA σε κανονική έκφραση

Thumbnail Image
Date
2022-10
Authors
Τράμπαρης, Ζήσης-Στυλιανός
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Στο πλαίσιο της παρούσας διπλωματικής αναπτύχθηκε εφαρμογή με γραφικό περιβάλλον για τη μετατροπή δοσμένου Μη Ντετερμινιστικού Πεπερασμένου Αυτομάτου (Non-deterministic Finite Automaton – NFA) σε ισοδύναμη κανονική έκφραση (Regular expression). Η μετατροπή πεπερασμένου αυτομάτου σε ισοδύναμη κανονική έκφραση είναι πάντα εφικτή. Η σχετική κατασκευαστική διαδικασία-απόδειξη αποτελεί μέρος της ύλης μαθημάτων στην περιοχή της Θεωρίας Υπολογισμού αλλά ανακύπτει συχνά στην πράξη και σε πραγματικές περιστάσεις. Σκοπός της εφαρμογής είναι να υποστηρίξει τόσο πρακτικές εφαρμογές που απαιτούν τη μετατροπή NFA σε ισοδύναμη κανονική έκφραση όσο και κάθε εκπαιδευτική διαδικασία που περιλαμβάνει τη διδασκαλία και εκπαίδευση στη μέθοδο μετατροπής NFA σε ισοδύναμη κανονική έκφραση. Η εφαρμογή δέχεται σαν είσοδο ένα πεπερασμένο αυτόματο και επιστρέφει μια ισοδύναμη κανονική έκφραση δίνοντας επιπλέον τη δυνατότητα για παρακολούθηση της διαδικασίας μετατροπής. Η εισαγωγή του αρχικού αυτομάτου, που αποτελεί την είσοδο στην εφαρμογή, γίνεται με γραφικό τρόπο. Εκτός από τον άμεσο υπολογισμό κανονικής έκφρασης ισοδύναμης με το δοσμένο Μη Ντετερμινιστικό Πεπερασμένο Αυτόματο (Non-deterministic Finite Automaton – NFA), η εφαρμογή που αναπτύχθηκε παρέχει επιπλέον τη δυνατότητα παρακολούθησης της διαδικασίας σταδιακής μετατροπής του αρχικού NFA σε ισοδύναμη κανονική έκφραση. Η εφαρμογή υλοποιήθηκε στη δημοφιλή πλατφόρμα ανάπτυξης γραφικών εφαρμογών Unity με συμπληρωματική χρήση της γλώσσας προγραμματισμού C# για τη διαχείριση των λειτουργιών των γραφικών αντικειμένων και την υλοποίηση των επιμέρους λειτουργιών της εφαρμογής. Τα γραφικά υποστηρίχτηκαν από τις βιβλιοθήκες γραφικών DirectX 11 που ενσωματώνει η Unity. Η συγγραφή του κώδικα έγινε στην πλατφόρμα Visual Studio. Για την σχεδίαση εικονιδίων και γραφικών αντικειμένων χρησιμοποιήθηκε το πρόγραμμα επεξεργασίας γραφικών Gimp.
Description
Keywords
Κανονικές εκφράσεις, Μετατροπή, Ψηφιακές εφαρμογές
Citation