Ποια είναι μερικά παραδείγματα κανονικών γλωσσών και πώς καθορίζονται στο πλαίσιο της επίσημης θεωρίας της γλώσσας;

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

Ποιες είναι οι κανονικές γλώσσες;

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

* Τακτικές εκφράσεις: Ένα μοτίβο που ορίζει ένα σύνολο χορδών.

* ντετερμινιστικά πεπερασμένα αυτοματοποιημένα (DFA): Ένα μηχάνημα που διαβάζει την είσοδο ένα σύμβολο κάθε φορά και μεταβαίνει μεταξύ των καταστάσεων με βάση την είσοδο. Αποδέχεται ή απορρίπτει την είσοδο με βάση την τελική κατάσταση.

* Μη deterministic Finite Automata (NFA): Παρόμοια με τα DFAs, αλλά επιτρέπουν πολλαπλές πιθανές μεταβάσεις από μια κατάσταση για ένα δεδομένο σύμβολο εισόδου (ή ακόμα και μεταβάσεις χωρίς να διαβάζουν οποιαδήποτε είσοδο).

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

Αυτές οι τέσσερις αναπαραστάσεις είναι ισοδύναμες. Εάν μπορείτε να ορίσετε μια γλώσσα με ένα από αυτά, μπορείτε να την ορίσετε με όλα αυτά. Αυτό είναι ένα θεμελιώδες θεώρημα στη θεωρία της επίσημης γλώσσας.

Παραδείγματα κανονικών γλωσσών

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

1. Η γλώσσα όλων των χορδών πάνω από {0, 1} που αρχίζουν με ένα '1'.

* Κανονική έκφραση: `1 (0 | 1)*` (ή `1 [01]*`)

* `1` ταιριάζει με το απαιτούμενο '1' στην αρχή.

* `(0 | 1)` σημαίνει "0 ή 1".

* `*` σημαίνει "μηδέν ή περισσότερα περιστατικά της προηγούμενης ομάδας."

* dfa:

`` `

0 1

-> Q0 Q1 Q1 (Q0 είναι η κατάσταση έναρξης)

Q1 Q1 Q1 (Q1 είναι μια κατάσταση αποδοχής)

`` `

* `q0` είναι η αρχική κατάσταση. Εάν η είσοδος ξεκινά με το «1», μεταβαίνει στην κατάσταση αποδοχής «Q1». Εάν ξεκινά με «0», μετακινείται στην κατάσταση που δεν έχει αποδοθεί (νεκρή).

* `Q1` είναι η κατάσταση αποδοχής. Μόλις φτάσει σε αυτή την κατάσταση, παραμένει σε αυτό, αποδεχόμενος περαιτέρω εισροές.

* nfa: Ένα NFA μπορεί να κατασκευαστεί ομοίως, αλλά μπορεί να έχει μια εναλλακτική πορεία από την κατάσταση εκκίνησης.

* Κανονική γραμματική: (Δεξιά-γραμμική)

`` `

S -> 1α

A -> 0a | 1Α | ε

`` `

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

* `A` δημιουργεί οποιοδήποτε συνδυασμό 0s και 1s, συμπεριλαμβανομένης της κενής συμβολοσειράς (ε).

2. Η γλώσσα όλων των χορδών πάνω από {a, b} που περιέχουν το υποσύνολο "aba".

* Κανονική έκφραση: `(a | b)*aba (a | b)*` (ή `[ab]*aba [ab]*`)

* `(a | b)*` ταιριάζει με οποιαδήποτε ακολουθία 'a's και' b (μηδέν ή περισσότερο).

* `aba` ταιριάζει με το απαιτούμενο υπόστρωμα.

* dfa: Αυτό το DFA θα έχει κράτη για να εντοπίσει την πρόοδο της αντιστοίχισης "ABA":

`` `

Α Β

-> Q0 Q1 Q0

Ε1 Q1 Q2

Ε2 Q1 Q0

Q3 Q3 Q3 (Q3 είναι μια κατάσταση αποδοχής)

`` `

* `q0`:αρχική κατάσταση. Αντιπροσωπεύει ότι δεν έχουμε δει κανένα μέρος του "aba".

* `Q1`:αντιπροσωπεύει ότι έχουμε δει" Α ".

* `q2`:αντιπροσωπεύει ότι έχουμε δει" ab ".

* `q3`:αντιπροσωπεύει ότι έχουμε δει" aba "(αποδοχή του κράτους). Μόλις στο `Q3`, οποιαδήποτε περαιτέρω είσοδος το διατηρεί στο` Q3`.

* nfa: Ένα NFA μπορεί να είναι απλούστερο για την κατασκευή αυτής της γλώσσας. Μπορεί να "μαντέψει" όταν μπορεί να ξεκινήσει το υπόστρωμα "ABA".

* Κανονική γραμματική:

`` `

S -> ως | BS | αα

A -> BB

B -> AC

C -> AC | π.Χ. | ε

`` `

3. Η γλώσσα όλων των χορδών πάνω από το {0, 1} με έναν ομοιόμορφο αριθμό 0s

* Κανονική έκφραση: `1*(01*01*)*`

* `1*`:μηδέν ή περισσότερα

*`01*01*`:Αυτό σημαίνει ότι η συμβολοσειρά θα πρέπει να έχει ένα ομοιόμορφο αριθμό 0s, καθώς κάθε 0 πρέπει να ακολουθείται από `1*01*`, έτσι είναι ζευγαρωμένο.

* dfa:

`` `

0 1

-> Q0 Q1 Q0 (Q0 είναι η κατάσταση έναρξης και αποδοχής)

Q1 Q0 Q1 (Q1 είναι μια μη αποδιδόμενη κατάσταση)

`` `

* `q0`:Ακόμη και ο αριθμός των 0s (εκκίνηση και αποδοχή κατάστασης).

* `Q1`:περίεργος αριθμός 0s.

* nfa: Ένα NFA μπορεί να κατασκευαστεί, αλλά το DFA είναι συχνά η πιο απλή αναπαράσταση.

* Κανονική γραμματική:

`` `

S -> 1S | 0A | ε

A -> 1A | 0S

`` `

4. Η γλώσσα που αποτελείται από τη συμβολοσειρά "γεια".

* Κανονική έκφραση: «Γεια»

* dfa:

`` `

h e l l o

-> Q0 Q1 - - - - (Q0 είναι η κατάσταση έναρξης)

Q1 - Q2 - - -

Q2 - - Q3 - -

Q3 - - - Q4 -

Q4 - - - - Q5

Q5 - - - - - (Q5 είναι μια κατάσταση αποδοχής)

`` `

* Κανονική γραμματική:

`` `

S -> χα

A -> EB

B -> LC

C -> LD

Δ -> Ο

`` `

Παραδείγματα γλωσσών που δεν είναι τακτικές

Αυτές οι γλώσσες * δεν μπορούν να εκπροσωπούνται από κανονικές εκφράσεις, DFAs, NFAs ή κανονικές γραμματικές. Απαιτούν πιο ισχυρούς φορμαλισμούς όπως γραμματικές χωρίς περιβάλλοντα ή μηχανές Turing.

1. Η γλώσσα των χορδών με ίσο αριθμό «Α και« Β είναι: {ε, AB, BA, AABB, ABAB, BABA, BBAA, ...}

2. Η γλώσσα των palindromes (χορδές που διαβάζουν τα ίδια προς τα εμπρός και πίσω): {ε, a, b, aa, bb, aba, bab, abba, ...}

3. Η γλώσσα {a n B n | n> =0} :Οι χορδές με το `n` 'Α ακολουθούνται από το` n`' b's (π.χ. ε, ab, aabb, aaabbb, ...). Αυτό είναι ένα κλασικό παράδειγμα που χρησιμοποιείται συχνά για να αποδείξει τους περιορισμούς των τακτικών γλωσσών.

4. Η γλώσσα {a n B m c n | n, m> =0} :Συμβολοσειρές με `n` a's, ακολουθούμενα από 'm` b και` n` c's. Αυτό είναι μη κανονικό.

Γιατί αυτές οι γλώσσες δεν είναι τακτικές;

Ο βασικός περιορισμός των τακτικών γλωσσών είναι η ανικανότητά τους να "μετρούν" ή "να θυμάστε" ένα αυθαίρετο ποσό πληροφοριών. Ένα DFA, NFA ή η κανονική έκφραση έχει έναν πεπερασμένο αριθμό καταστάσεων ή συμβόλων. Για να αναγνωρίσετε γλώσσες όπως {a n B n }, θα πρέπει να παρακολουθείτε τον αριθμό των «Α που έχετε δει για να εξασφαλίσετε ότι υπάρχει ο ίδιος αριθμός« Β. Ένα πεπερασμένο αυτόματο αυτόματο δεν έχει την ικανότητα μνήμης να το κάνει αυτό για αυθαίρετα μεγάλο «n». Αυτή η διαίσθηση είναι επίσημη από το *αντλημένο λεμμά για κανονικές γλώσσες *, ένα ισχυρό εργαλείο για να αποδείξει ότι μια γλώσσα δεν είναι *κανονική.

Συνοπτικά

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