Ποια είναι μερικά παραδείγματα γλωσσών χωρίς περιβάλλοντα και πώς διαφορετικά από άλλες γλώσσες τύπων;

Εντάξει, ας βυθίσουμε σε γλώσσες χωρίς περιβάλλοντα (CFLs) και πώς στοιβάζονται ενάντια σε άλλες τάξεις γλώσσας.

Ποιες είναι οι γλώσσες χωρίς περιβάλλοντα (CFLs);

Μια γλώσσα χωρίς περιβάλλον είναι μια επίσημη γλώσσα που μπορεί να δημιουργηθεί από μια γραμματική χωρίς περιβάλλον (CFG). Ένα CFG αποτελείται από:

* Ένα σύνολο μη τερματικών συμβόλων (μεταβλητές): Αυτά αντιπροσωπεύουν συντακτικές κατηγορίες (π.χ., "πρόταση", "ουσιαστική φράση", "φράση ρήματος").

* Ένα σύνολο συμβόλων τερματικού: Αυτά είναι τα πραγματικά σύμβολα που συνθέτουν τις χορδές της γλώσσας (π.χ. γράμματα, ψηφία, στίξη).

* Ένα σύνολο κανόνων παραγωγής: Αυτά καθορίζουν τον τρόπο με τον οποίο τα μη τερματικά μπορούν να ξαναγραφούν ως αλληλουχίες τερματικών και μη τερματικών. Ένας κανόνας παραγωγής έχει τη μορφή `a-> α ', όπου το` a` είναι μη τερματικό και το `α' είναι μια σειρά από τερματικά ή/και μη τερματικά. Η αριστερή πλευρά κάθε παραγωγής πρέπει να είναι ένα μόνο μη τερματικό.

* Ένα σύμβολο εκκίνησης: Ένα μη τερματικό που αντιπροσωπεύει την αρχή της παραγωγής.

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

Παραδείγματα γλωσσών χωρίς περιβάλλοντα:

1. Αυτή η γλώσσα αποτελείται από συμβολοσειρές όπου ο αριθμός των «Α είναι ίσος με τον αριθμό των« Β και όλα τα «Α έρχονται ενώπιον όλων των« Β. Παραδείγματα:"", "ab", "aabb", "aaabbb".

* Ένα CFG για αυτήν τη γλώσσα είναι:

`` `

S -> ASB | ε (ε αντιπροσωπεύει την κενή συμβολοσειρά)

`` `

* Επεξήγηση:

* `S 'είναι το σύμβολο εκκίνησης.

* Ο κανόνας `s -> asb` προσθέτει αναδρομικά ένα 'a' στην αρχή και ένα« b »στο τέλος, εξασφαλίζοντας ότι είναι πάντοτε ταιριάζουν.

* Ο κανόνας `s -> ε` παρέχει τη βασική περίπτωση, επιτρέποντας να σταματήσει η παραγωγή.

2. Palindromes: Η γλώσσα των παλινδρόμων πάνω από κάποιο αλφάβητο (π.χ. {a, b}). Ένα Palindrome διαβάζει τα ίδια προς τα εμπρός και προς τα πίσω. Παραδείγματα:"", "Α", "Β", "ΑΑ", "BB", "Aba", "Abba", "Racecar".

* Ένα CFG για palindromes πάνω από {a, b} είναι:

`` `

S -> asa | BSB | α | B | ε

`` `

* Επεξήγηση:

* `S 'είναι το σύμβολο εκκίνησης.

* `S -> asa` προσθέτει 'a' και στα δύο άκρα.

* `S -> bsb` προσθέτει 'b' και στα δύο άκρα.

* `S -> a`,` s -> b`, και `s -> ε, παρέχουν τις βασικές περιπτώσεις.

3. ισορροπημένες παρενθέσεις: Η γλώσσα των χορδών με ισορροπημένες παρενθέσεις (π.χ., "()", "(())", "() ()").

* Ένα CFG για ισορροπημένες παρενθέσεις είναι:

`` `

S -> (s) s | ε

`` `

* Επεξήγηση:

* `S 'είναι το σύμβολο εκκίνησης.

* `S -> (s) S` δημιουργεί ένα ζευγάρι αντίστοιχων παρενθέσεων που περικλείουν μια άλλη ισορροπημένη συμβολοσειρά, ακολουθούμενη από μια άλλη ισορροπημένη συμβολοσειρά. Αυτό επιτρέπει τη φωλιά και τη συγκόλληση των ισορροπημένων παρενθέσεων.

* `S -> ε` είναι η βασική περίπτωση (η κενή συμβολοσειρά θεωρείται ισορροπημένη).

4. Αριθμικές εκφράσεις: Η γλώσσα των έγκυρων αριθμητικών εκφράσεων με χειριστές όπως +, -, *, /, και παρενθέσεις.

* Ένα απλοποιημένο CFG (χωρίς προτεραιότητα χειριστή) θα μπορούσε να είναι:

`` `

E -> E + E | E - E | E * E | E / e | Ε) | ταυτότητα

`` `

όπου το `id` αντιπροσωπεύει ένα αναγνωριστικό (μεταβλητό όνομα ή αριθμός).

* Θα χρειαζόταν ένα πιο περίπλοκο CFG για την επιβολή της προτεραιότητας και της συνεργασίας του χειριστή.

5. Η σύνταξη των περισσότερων γλωσσών προγραμματισμού (όπως το C, Java, Python) είναι σε μεγάλο βαθμό χωρίς περιεχόμενο. Οι μεταγλωττιστές χρησιμοποιούν τους parsers με βάση τα CFGs για να ελέγξουν τη δομή των προγραμμάτων. Υπάρχουν ορισμένες πτυχές των γλωσσών προγραμματισμού που δεν είναι ελεύθερες από το περιβάλλον (όπως η δήλωση μεταβλητής πριν από τη χρήση)

Πώς διαφέρουν οι CFL από άλλες τάξεις γλώσσας:

Για να κατανοήσουμε τη διαφορά, πρέπει να εξετάσουμε την ιεραρχία του Chomsky, η οποία ταξινομεί τις γλώσσες που βασίζονται στην πολυπλοκότητα των γραμματικών τους και των μηχανών που μπορούν να τις αναγνωρίσουν:

* Τακτικές γλώσσες:

* Ορίζεται από τακτικές εκφράσεις ή πεπερασμένα αυτοματοποιημένα στοιχεία (FAS).

* Λιγότερο ισχυρό από τα CFLs.

* Μπορεί να αναγνωρίσει απλά μοτίβα, αλλά δεν μπορεί να χειριστεί τις ένθετες δομές ή την καταμέτρηση.

* * Παράδειγμα κανονικής γλώσσας:* χορδές που περιέχουν "ab" (π.χ. "cab", "abab", "xyzab"). Η γλώσσα `a*b*` (οποιοσδήποτε αριθμός 'a που ακολουθείται από οποιοδήποτε αριθμό' b) είναι επίσης τακτική.

* * Βασική διαφορά:* Οι κανονικές γλώσσες μπορούν να παρακολουθούν μόνο μια πεπερασμένη ποσότητα πληροφοριών. Δεν μπορούν να "θυμηθούν" πόσα "Α έχουν δει για να εξασφαλίσουν ότι υπάρχει ο ίδιος αριθμός« Β.

* Γλώσσες ευαίσθητων στο περιβάλλον (CSLS):

* Πιο ισχυρό από τα CFLs.

* Αναγνωρίστηκε από γραμμικά οριοθετημένα αυτοματοποιημένα (LBAs).

* Οι κανόνες παραγωγής μπορούν να εξαρτώνται από το * πλαίσιο * του μη τερματικού που ξαναγράφηκε. Ένας κανόνας μπορεί να μοιάζει με «ααβ -> α -β», που σημαίνει «Α» μπορεί να ξαναγραφεί στο «γ» μόνο όταν είναι μεταξύ «α» και «β».

* * Παράδειγμα μιας ευαίσθητης στο περιβάλλον γλώσσα:* `a^n b^n c^n` (ίσος αριθμός 'a's', b και 'c είναι σε τάξη). Αυτό * δεν μπορεί να γίνει με ένα CFG.

* Αναδρομικά απαράδεκτες γλώσσες (rels) / turing-recognizable Γλώσσες:

* Πιο ισχυρή τάξη.

* Αναγνωρίστηκε από τις μηχανές Turing.

* Οποιαδήποτε γλώσσα που μπορεί να αναγνωριστεί από έναν αλγόριθμο είναι αναδρομικά απαράδεκτη.

Εδώ είναι ένας πίνακας που συνοψίζει τις βασικές διαφορές:

| Τάξη γλώσσας | Ορισμός μηχανισμού | Automaton | Εκφραστική δύναμη | Παραδείγματα |

| ------------------------------- | ------------------------------------------------------------ ------------------------------------------- ------------------------------------------------------------------- -----------------------------------------------------------------------------------------------------------------------------------------------

| Τακτικές γλώσσες | Τακτικές εκφράσεις/FAS | Πεπερασμένο Automaton | Απλούστερα μοτίβα, πεπερασμένη μνήμη | `a*b*`, χορδές που περιέχουν "ab" |

| Γλώσσες χωρίς περιβάλλοντα | Γραμματική χωρίς περιβάλλοντα | Automaton (PDA) Ένθετες δομές, περιορισμένη μέτρηση (χρησιμοποιώντας μια στοίβα) `a^n b^n`, palindromes, ισορροπημένες παρενθέσεις, σύνταξη γλώσσας προγραμματισμού |

| Ευαίσθητο στο περιβάλλον L | Γραμματική ευαίσθητη στο περιβάλλον | Γραμμική οριοθετημένη αυτοματοποιημένη | Πιο σύνθετες εξαρτήσεις | `a^n b^n c^n` |

| Αναδρομικά απαράδεκτα | Μηχανή Turing | Μηχανή Turing | Οποιαδήποτε υπολογιστική γλώσσα | Σταματήστε τις λύσεις προβλημάτων |

Γιατί τα CFLs είναι σημαντικά;

* Γλώσσες προγραμματισμού: Όπως αναφέρθηκε, αποτελούν το θεμέλιο για τη σύνταξη της γλώσσας προγραμματισμού. Οι μεταγλωττιστές χρησιμοποιούν εργαλεία που παράγουν parsers από CFGs (π.χ., YACC, Bison).

* Επεξεργασία φυσικής γλώσσας: Ενώ οι φυσικές γλώσσες δεν είναι αυστηρά χωρίς περιβάλλον, τα CFG είναι μια χρήσιμη προσέγγιση για τη μοντελοποίηση ορισμένων πτυχών της δομής των προτάσεων.

* Δομές δεδομένων: Τα CFL μπορούν να μοντελοποιήσουν τη δομή ορισμένων δομών δεδομένων, όπως το XML ή το JSON.

* Θεωρητική επιστήμη υπολογιστών: Είναι ένας κρίσιμος τομέας σπουδών στη θεωρία των αυτοματοποιημένων και την επίσημη θεωρία της γλώσσας, γεφυρώνοντας το χάσμα μεταξύ των κανονικών γλωσσών (απλούστερων) και των ευαίσθητων σε περιβάλλοντα γλώσσες (πιο πολύπλοκες).

Παράδειγμα που απεικονίζει τη διαφορά (a^n b^n vs. a^n b^n c^n):

* `a^n b^n` είναι χωρίς περιβάλλον: Όπως είδαμε, μπορούμε εύκολα να γράψουμε ένα CFG για αυτό χρησιμοποιώντας τη συμπεριφορά που μοιάζει με στοίβα των κανόνων παραγωγής CFG. Το CFG μπορεί να "θυμηθεί" τον αριθμό των «Α, πιέζοντάς τα εννοιολογικά σε μια στοίβα, και στη συνέχεια« ταιριάζει »το καθένα« Β »με το να σκάσει ένα« Α »από τη στοίβα.

* `a^n b^n c^n` δεν είναι χωρίς περιβάλλον: Αυτή η γλώσσα απαιτεί την ανάμνηση * δύο * μετράει (τον αριθμό των 'a και τον αριθμό των' b) για να εξασφαλίσει ότι είναι ίσοι με τον αριθμό των 'c. Ένα PDA, με την ενιαία στοίβα του, δεν μπορεί να το κάνει άμεσα. Για να αποδείξετε ότι δεν είναι απαλλαγμένη από το περιβάλλον, θα χρησιμοποιούσατε συνήθως το λεμμά για την άντληση για γλώσσες χωρίς περιβάλλοντα.

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