Στη σημερινή τεχνολογική εποχή τόσο ο τομέας του υλικού όσο και του λογισμικού έχει σημειώσει τεράστια ανάπτυξη. Ένας από τους σημαντικότερους τομείς ανάπτυξης παρατηρήθηκε στις μεθόδους σχεδιασμού υλικού. Με την αναπτυσσόμενη τεχνολογία , ήταν δυνατή η εφαρμογή της έννοιας του Σχεδιασμού Υλικού - Λογισμικού. Αναπτύσσονται διάφορες μέθοδοι με τις οποίες, χρησιμοποιώντας λογισμικό μπορεί κανείς να σχεδιάσει και να προσομοιώσει πλήρως τα συστήματα υλικού. Μία από αυτές τις μεθόδους είναι η Θεωρία Automata. Η θεωρία Automata είναι ο κλάδος της επιστήμη των υπολογιστών που ασχολείται με το σχεδιασμό του αφηρημένου μοντέλου υπολογιστικών συσκευών που ακολουθούν αυτόματα την προκαθορισμένη ακολουθία βημάτων. Αυτό το άρθρο περιγράφει σύντομες πληροφορίες σχετικά με το σεμινάριο αυτόματων.

Τι είναι η θεωρία Automata;

Η λέξη Automata προέρχεται από τα ελληνικά, που σημαίνει «αυτο-δράση». Το Automaton είναι ένα μαθηματικό μοντέλο της μηχανής. Το Automaton αποτελείται από καταστάσεις και μεταβάσεις. Καθώς η είσοδος δίνεται στο αυτόματο κάνει μια μετάβαση στην επόμενη κατάσταση, ανάλογα με τη λειτουργία μετάβασης. Οι είσοδοι στη συνάρτηση μετάβασης είναι παρούσα κατάσταση και πρόσφατα σύμβολα. Εάν ένα Automaton έχει έναν πεπερασμένο αριθμό καταστάσεων, είναι γνωστό ως Finite Automata ή Μηχανή πεπερασμένης κατάστασης . Τα πεπερασμένα αυτόματα αντιπροσωπεύονται από ένα 5-tuple (Q, ∑, δ, qo, F)

Που,

Q = Πεπερασμένο σύνολο καταστάσεων.

∑ = πεπερασμένο σύνολο συμβόλων που ονομάζεται επίσης Αλφάβητο των αυτόματων.

δ = η συνάρτηση μετάβασης.

qo = αρχική κατάσταση της εισαγωγής.

F = σύνολο τελικών καταστάσεων του Q.

Βασικές ορολογίες της θεωρίας Automata

Μερικές από τις βασικές ορολογίες της Θεωρίας Automata είναι-

1 . Αλφάβητο : Οποιοδήποτε πεπερασμένο σύνολο συμβόλων στη θεωρία automata είναι γνωστό ως Αλφάβητο. Αντιπροσωπεύεται από το γράμμα ∑ το σετ {a, b, c, d, e,} ονομάζεται σετ αλφαβήτου, ενώ τα γράμματα του συνόλου 'a', 'b', 'c', 'd', 'e' ονομάζονται σύμβολα.

δύο . Σειρά : Στα αυτόματα στοιχεία, μια συμβολοσειρά είναι μια πεπερασμένη ακολουθία συμβόλων που λαμβάνονται από το σύνολο αλφαβήτου ∑, Για παράδειγμα, η συμβολοσειρά S = «adeaddadc» ισχύει στο αλφάβητο σύνολο∑ = {a, b, c, d, e,}.

“διακόπτης διπλού πόλου διπλή ρίψη ”

3 . Μήκος χορδής : Ο αριθμός των συμβόλων που υπάρχουν στη συμβολοσειρά είναι γνωστός ως Μήκος συμβολοσειράς. Για τη συμβολοσειρά S = 'adaada' το μήκος της συμβολοσειράς είναι | S | = 6. Εάν το μήκος της συμβολοσειράς είναι 0, τότε ονομάζεται κενή συμβολοσειρά.

4 . Kleen Star : Είναι ο ενιαίος τελεστής στο σύνολο συμβόλων Σ, που δίνει το άπειρο σύνολο όλων των πιθανών χορδών, συμπεριλαμβανομένου του λ, όλων των πιθανών μηκών πάνω από το σύνολο Σ. Αντιπροσώπευε ο. Για παράδειγμα, για το σύνολο Σ = {c, d}, ∑ * = {λ, c, d, cd, dc, cc, dd, ……}.

5 . Κλείσιμο Kleen : Είναι το άπειρο σύνολο όλων των πιθανών χορδών του συνόλου αλφαβήτου εκτός από το λ. Δηλώνεται με. Για το σύνολο Σ = {a, d}, ∑ + = {a, d, ad, da, aa, dd,… ..}.

6 . Γλώσσα : Η γλώσσα είναι το υποσύνολο του αστεριού Kleene setene * για κάποιο σύνολο αλφαβήτου Σ. Η γλώσσα μπορεί να είναι πεπερασμένη ή άπειρη. Για παράδειγμα, εάν μια γλώσσα παίρνει όλες τις πιθανές συμβολοσειρές μήκους 2 πάνω από το σύνολο Σ = {a, d}, τότε L = {aa, ad, da, dd}.

Τυπικές γλώσσες και αυτόματα

Στη θεωρία automata, η επίσημη γλώσσα είναι ένα σύνολο συμβολοσειρών, όπου κάθε συμβολοσειρά είναι αποτελείται από σύμβολα ανήκει στο πεπερασμένο σετ αλφαβήτου Σ. Ας εξετάσουμε μια γλώσσα γάτας, η οποία μπορεί να περιέχει οποιεσδήποτε χορδές από το παρακάτω άπειρο σετ…
νιαούρισμα!
Μουβ!
mewww !! ……

Το σετ αλφαβήτου για τη γλώσσα της γάτας είναι Σ = {m, e, w,!}. Αφήστε αυτό το σετ να χρησιμοποιηθεί για μοντέλο πεπερασμένης κατάστασης Automata-m. Στη συνέχεια, η επίσημη γλώσσα που χαρακτηρίζεται από το μοντέλο m συμβολίζεται με

Λ (μ)
L (m) = {‘mew!’, ‘Meww!’, ‘Mewww’, ……}

Το Automaton είναι χρήσιμο για τον ορισμό μιας γλώσσας επειδή μπορεί να εκφράσει ένα άπειρο σύνολο σε κλειστή μορφή. Οι επίσημες γλώσσες δεν είναι οι ίδιες με τις φυσικές γλώσσες που μιλάμε στην καθημερινή μας ζωή. Μια επίσημη γλώσσα μπορεί να δηλώσει τις διάφορες καταστάσεις του μηχανήματος, σε αντίθεση με τις κανονικές γλώσσες μας. Η επίσημη γλώσσα χρησιμοποιείται για τη μοντελοποίηση ενός μέρους της φυσικής γλώσσας, όπως η σύνταξη κ.λπ.… Οι επίσημες γλώσσες ορίζονται από αυτόματα δεδομένα πεπερασμένης κατάστασης. Υπάρχουν δύο κύριες προοπτικές των αυτόματων καταστάσεων πεπερασμένων - Αποδέκτες που μπορούν να πουν εάν μια συμβολοσειρά είναι στη γλώσσα και η δεύτερη είναι η γεννήτρια που παράγει μόνο τις χορδές στη γλώσσα.

“πώς λειτουργούν τα παγκόσμια συστήματα εντοπισμού θέσης ”

Ντετερμινιστικά πεπερασμένα αυτόματα

Στον ντετερμινιστικό τύπο αυτόματων, όταν δίνεται μια είσοδος, μπορούμε πάντα να καθορίσουμε σε ποια κατάσταση θα ήταν η μετάβαση. Δεδομένου ότι αυτό είναι ένα πεπερασμένο αυτόματο, ονομάζεται Deterministic Finite Automata.

ΓΡΑΦΙΚΗ ΑΝΑΠΑΡΑΣΤΑΣΗ

Το State Diagram είναι τα γραφήματα που χρησιμοποιούνται για γραφική αναπαράσταση του Ντετερμινιστικού Πεπερασμένου Αυτοματισμού. Ας καταλάβουμε με ένα παράδειγμα. Αφήστε τα ντετερμινιστικά πεπερασμένα αυτόματα να…
Q = {a, b, c, d}.
Σ = {0, 1}
= {α}
F = {d} και η συνάρτηση μετάβασης είναι

Φόρμα πίνακα γραφικής παράστασης

Διάγραμμα κατάστασης

Διάγραμμα κατάστασης ντετερμινιστικών αυτόματων πεπερασμένων καταστάσεων

Από το διάγραμμα κατάστασης

Τα κράτη αντιπροσωπεύονται από κορυφές.
Οι μεταβάσεις αντιπροσωπεύονται από το τόξο με την ένδειξη αλφαβήτου.
Το κενό μονό εισερχόμενο τόξο αντιπροσωπεύει την αρχική κατάσταση.
Η κατάσταση με διπλούς κύκλους είναι η τελική κατάσταση.

Μη ντετερμινιστικά πεπερασμένα αυτόματα

Τα αυτόματα δεδομένα όπου η κατάσταση εξόδου για τη δεδομένη είσοδο δεν μπορεί να προσδιοριστεί ονομάζεται μη-αποφασιστικά αυτόματα. Ονομάζεται επίσης Μη-Ντετερμινιστική Πεπερασμένη Αυτοματοποίηση, καθώς έχει έναν πεπερασμένο αριθμό κρατών. Τα μη ντετερμινιστικά πεπερασμένα Automata αντιπροσωπεύονται ως το σύνολο 5 –πλού όπου (Q, ∑, δ, qo, F)

Ε = πεπερασμένο σύνολο κρατών.
∑ = Σετ αλφαβήτου.
δ= η συνάρτηση μετάβασης

που : qo = Αρχική κατάσταση.

ΓΡΑΦΙΚΗ ΑΝΑΠΑΡΑΣΤΑΣΗ

Τα μη ντετερμινιστικά πεπερασμένα αυτόματα παρουσιάζονται με τη βοήθεια του διαγράμματος κατάστασης. Αφήστε τα μη-ντετερμινιστικά πεπερασμένα αυτόματα

Ε = {α, β, γ, δ}
Σ = {0,1}
qo = {α}
F = {d}

Οι μεταβάσεις είναι

Φόρμα πίνακα γραφικής παράστασης

“Οι ενσύρματες συνδέσεις LAN χρησιμοποιούν ένα πρότυπο πρωτοκόλλου που ονομάζεται ethernet για επικοινωνία. ”

Διάγραμμα κατάστασης

Διάγραμμα κατάστασης μη-ντετερμινιστικών πεπερασμένων αυτομάτων

Εφαρμογές θεωρίας Automata

Οι εφαρμογές του θεωρία automata συμπεριλάβετε τα ακόλουθα.

Η θεωρία Automata είναι πολύ χρήσιμη στους τομείς της Θεωρίας του υπολογισμού, των παραγωγών μεταγλωττιστών, του AI κ.λπ.
Για μεταγλωττιστές επεξεργασίας κειμένου και σχέδια υλικού, τα πεπερασμένα αυτόματα παίζουν σημαντικό ρόλο.
Για εφαρμογές σε AI και σε γλώσσες προγραμματισμού , Η γραμματική χωρίς περιεχόμενο είναι πολύ χρήσιμη.
Στον τομέα της βιολογίας, τα κυτταρικά αυτόματα είναι χρήσιμα.
Στη θεωρία των πεπερασμένων πεδίων μπορούμε επίσης να βρούμε την εφαρμογή του Automata.

Σε αυτό το άρθρο, μάθαμε μια σύντομη εισαγωγή στις γλώσσες και τον υπολογισμό της θεωρίας automata. Τα Automata υπήρχαν από την προϊστορική περίοδο. Με την εφεύρεση νέων τεχνολογιών εμφανίζονται πολλές νέες εξελίξεις σε αυτόν τον τομέα. Με ποιον τύπο αυτόματων συναντήθηκε;