Γραμματική, γλώσσα και οι αποδέκτες τους στο Automata » CS Taleem

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

Τύποι Γραμματικών

Υπάρχουν τέσσερις κύριοι τύποι γραμματικών στη θεωρία των Automata.

• Κανονική Γραμματική
• Ελεύθερη γραμματική περιβάλλοντος
• Context Sensitive Grammar
• Απεριόριστη Γραμματική

Ας εξηγήσουμε λεπτομερώς όλους τους παραπάνω τύπους γραμματικών.

1. Κανονική γραμματική (RL)

Το Regular Grammar δημιουργεί τις Κανονικές Γλώσσες και όλες οι κανονικές γλώσσες γίνονται δεκτές από το Finite Automata Machine. Η κανονική γραμματική ονομάζεται επίσης γραμματική τύπου 3

Οι κανονικές γλώσσες είναι δύο τύπων

1. Πεπερασμένες κανονικές γλώσσες
2. Άπειρες κανονικές γλώσσες

Το Finite Automata Machine είναι επίσης δύο τύπων

1. Ντετερμινιστικά πεπερασμένα αυτόματα (DFA)
2. Μη ντετερμινιστικά πεπερασμένα αυτόματα (NDFA)

Όλες οι κανονικές γλώσσες είτε πεπερασμένες είτε άπειρες γίνονται αποδεκτές από το NDFA. Αλλά όλες οι κανονικές γλώσσες και κάποια άπειρη γλώσσα γίνονται δεκτές από το DFA.

2. Ελεύθερη γραμματική περιβάλλοντος (CFG)

Το Context free Grammar δημιουργεί τις Γλώσσες χωρίς περιβάλλον και όλες οι γλώσσες χωρίς περιβάλλον γίνονται αποδεκτές από το Pushdown Automata Machine. Η ελεύθερη γραμματική περιβάλλοντος ονομάζεται επίσης γραμματική τύπου 2

Οι ελεύθερες γλώσσες περιβάλλοντος είναι δύο τύπων

1. Ντετερμινιστικό πλαίσιο Ελεύθερες γλώσσες
2. Μη ντετερμινιστικές ελεύθερες γλώσσες

Το Pushdown Automata Machine είναι επίσης δύο τύπων

1. Deterministic Pushdown Automata (DPDA)
2. Μη-ντετερμινιστικά αυτόματα Pushdown (NPDA)

Όλες οι ελεύθερες γλώσσες Deterministic Context γίνονται δεκτές από Deterministic Pushdown Automata (DPDA). Όμως, όλες οι μη-ντετερμινιστικές ελεύθερες γλώσσες γίνονται αποδεκτές από τα Μη ντετερμινιστικά Pushdown Automata (NPDA).

3. Context Sensitive Grammar (CSG)

Το Context Sensitive Grammar δημιουργεί το Γλώσσες ευαίσθητες σε περιβάλλον και όλες οι ευαίσθητες γλώσσες γίνονται αποδεκτές από Μηχανή Automata Linear Bound. Η ελεύθερη γραμματική περιβάλλοντος ονομάζεται επίσης γραμματική τύπου 1.

Σημείωση: Οι ευαίσθητες γλώσσες περιβάλλοντος και οι μηχανές τους δεν είναι ντετερμινιστικές και μη ντετερμινιστικές.

4. Απεριόριστη Γραμματική

Η Απεριόριστη Γραμματική δημιουργεί τις Αναδρομικές Αριθμήσιμες Γλώσσες και όλες οι Αναδρομικές Αριθμήσιμες Γλώσσες γίνονται δεκτές από το Turing Machine. Η απεριόριστη γραμματική ονομάζεται επίσης γραμματική τύπου 0.

Σπουδαίος: Τύπος-0 Ο αποδέκτης είναι η υψηλότερη ισχύς και ο αποδέκτης τύπου 3 έχει τη χαμηλότερη ισχύ. Σημαίνει ότι ο αποδέκτης τύπου -3 που είναι η Μηχανή Turing μπορεί να δεχτεί όλες τις γλώσσες είτε είναι κανονικές, είτε είναι άνευ περιεχομένου είτε ευαίσθητες στο περιβάλλον. Αλλά ο αποδέκτης τύπου 3 που είναι τα πεπερασμένα αυτόματα μπορεί να δεχτεί μόνο κανονικές γλώσσες.

Ιεραρχία Τσόμσκι

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

Βοηθήστε τους άλλους Κοινοποιώντας…