Τυπικές γλώσσες

Η τυπική γλώσσα είναι μια γενίκευση της έννοιας της γλώσσας, που γνωρίζουμε από την καθημερινή ζωή.

Βασικές έννοιες

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

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

Λέξη, ή αλλιώς συμβολοσειρά, ονομάζουμε μια πεπερασμένη ακολουθία συμβόλων από ένα αλφάβητο Σ. Αν έχουμε για παράδειγμα το αλφάβητο Σ= {α,β,γ,δ,ε,…, ω}, τότε λέξη είναι για παράδειγμα η ακολουθία «γεια» ή «σκυλι», αλλά όχι «βράδυ» (δεν έχουμε το γράμμα «ά»), «Νίκος» (δεν έχουμε το γράμμα «Ν») ή «καλη μερα» (δεν έχουμε το κενό). Μήκος της λέξης ονομάζουμε το πλήθος των συμβόλων από τα οποία αποτελείται η λέξη.

Παράθεση λέξεων: αν έχουμε δύο λέξεις a = a₁a₂… a_n και b = b₁b₂… b_m, τότε με την παράθεση των λέξεων προκύπτει η λέξη ab = a₁a₂… a_nb₁b₂… b_m. Παράδειγμα: με την παράθεση των λέξεων «γεια» και «σκυλι» προκύπτει η λέξη «γειασκυλι». Την παράθεση τη συμβολίζουμε είτε με κυκλάκι, δηλαδή a ∘ b, είτε δεν τη συμβολίζουμε καθόλου και απλώς γράφουμε τις λέξεις τη μία μετά την άλλη, χωρίς ειδικό σύμβολο παράθεσης.

Κενή λέξη συμβολίζουμε με ε τη λέξη που έχει μήκος μηδέν. Αν παραθέσουμε τη λέξη a = a₁… a_n με την κενή λέξη ε, παίρνουμε πάλι τη λέξη a. Δηλαδή ισχύει a ∘ ε = a.

Κλειστότητα Kleene του αλφαβήτου Σ είναι το σύνολο όλων των λέξεων που μπορούμε να σχηματίσουμε από το αλφάβητο Σ, μαζί με την κενή λέξη. Την κλειστότητα τη συμβολίζουμε Σ^∗. Αν έχουμε το δυαδικό αλφάβητο Σ= {0, 1}, τότε ισχύει

$${\mathrm{\Sigma }}^{\ast }=\{\epsilon ,0,1,00,01,10,11,000,001,\dots \}$$

Μερικές φορές χρησιμοποιούμε και τη θετική κλειστότητα του αλφαβήτου, δηλαδή πάλι όλες τις λέξεις που μπορούμε να σχηματίσουμε από το αλφάβητο, εκτός από την κενή λέξη. Τη θετική κλειστότητα τη συμβολίζουμε Σ⁺ και ισχύει Σ⁺ = Σ^∗ ∖ {ε}.

Παραδείγματα αλφαβήτων

• Ας γυρίσουμε στο παράδειγμα με τα ελληνικά. Κάθε ελληνική λέξη βρίσκεται στην κλειστότητα του αλφαβήτου που περιέχει τα πεζά και τα κεφαλαία γράμματα και τις παραλλαγές με τόνους και διαλυτικά (και ίσως ακόμη την παύλα «-»). Αν σε αυτό το αλφάβητο προσθέσουμε και το κενό και τα σημεία στίξης (κόμμα, τελεία, θαυμαστικό, ερωτηματικό, …), παίρνουμε με την κλειστότητα όλες τις προτάσεις που μπορούμε να σχηματίσουμε στην ελληνική γλώσσα. Φυσικά, στην κλειστότητα θα ανήκουν και προτάσεις όπως «σδφλσφ κασδφ καγρτζεωψκ κφ φκτζβσγ!!!:;;: ::!;:;:σδφ», που όμως εξακολουθούν να είναι πιο ουσιαστικές από πολλά διοικητικά έγγραφα.

• Αν το αλφάβητό μας περιέχει όλα τα ψηφία Σ= {0, 1, …, 9}, τότε στην κλειστότητα θα βρίσκονται όλοι οι φυσικοί αριθμοί – και κάποια επιπλέον στοιχεία. Θα υπάρχουν δηλαδή και αριθμοί που αρχίζουν από μηδέν, π.χ. 00054, και επιπλέον θα υπάρχει η κενή λέξη, η οποία φυσικά δεν είναι κανένας αριθμός.

• Το αλφάβητο πρέπει να είναι μη κενό, άρα το μικρότερο αλφάβητο έχει τουλάχιστον ένα σύμβολο. Για παράδειγμα, για το αλφάβητο Σ= {!} θα παίρναμε την κλειστότητα Σ^∗ = {ε, !, !!, !!!, !!!!, …}, δηλαδή ένα σύνολο λέξεων, όπου για κάθε n ∈ ℕ υπάρχει στην κλειστότητα μια λέξη με n θαυμαστικά και καμία άλλη λέξη δεν θα υπάρχει στην κλειστότητα.

• Έστω Σ= {qw,c}. Αυτό είναι ένα πολύ περίεργο αλφάβητο, επειδή περιέχει τη λέξη qw. Αυτός ο συμβολισμός συνήθως δεν χρησιμοποιείται, επειδή μπερδεύει και είναι παράξενος, αλλά μπορούμε να το φανταστούμε έτσι: κολλάμε τα γράμματα «q» και «w» μεταξύ τους, ώστε να αποτελούν έναν χαρακτήρα. Τότε μπορούμε να δούμε τη λέξη «qw» ως σύμβολο «qw». Αν από αυτό το σύμβολο σχηματίσουμε τη λέξη «qwcqw», τότε αυτή η λέξη θα έχει μήκος τρία – θα αποτελείται από τα σύμβολα «qw», «c» και «qw». Δεν θα συναντήσουμε συχνά τέτοια αλφάβητα, υπάρχουν όμως περιπτώσεις όπου χρειάζεται να χρησιμοποιήσουμε σύμβολα που αποτελούνται από περισσότερα σύμβολα.

Τυπική γλώσσα

(Τυπική) γλώσσα πάνω από το αλφάβητο Σ είναι ένα οποιοδήποτε υποσύνολο του Σ^∗. Για μια γλώσσα L πάνω από το αλφάβητο Σ ισχύει λοιπόν L ⊆ Σ^∗. Παραδείγματα γλωσσών:

• Στο προηγούμενο μέρος ορίσαμε το αλφάβητο των ψηφίων Σ= {0, 1, …, 9}. Η κλειστότητα είναι όλες οι λέξεις που σχηματίζονται μόνο από ψηφία. Αν προσθέσουμε τον κανόνα ότι η λέξη δεν επιτρέπεται να αρχίζει από μηδέν και δεν επιτρέπεται να είναι κενή, παίρνουμε το σύνολο των θετικών φυσικών αριθμών ℕ^∗. Ισχύει η σχέση ℕ^∗ ⊆ Σ^∗, άρα το ℕ^∗ είναι γλώσσα πάνω από το αλφάβητο Σ.

• Στο προηγούμενο σύνολο ψηφίων μπορούμε να προσθέσουμε και τον χαρακτήρα μείον «-», οπότε Σ= {0, 1, …, 9, −}. Η κλειστότητα είναι όλες οι λέξεις που αποτελούνται από ψηφία ή από το σύμβολο μείον. Αυτό όμως σημαίνει ότι στην κλειστότητα υπάρχουν και λέξεις όπως «12-84-», «1-5-8» ή «-». Τη γλώσσα των ακεραίων ℤ τη δημιουργούμε προσθέτοντας τρεις κανόνες:

  • Ο χαρακτήρας μείον δεν εμφανίζεται καθόλου στη λέξη ή εμφανίζεται στην αρχή της λέξης.
  • Το πρώτο ψηφίο της λέξης δεν μπορεί να είναι μηδέν, εκτός από τη λέξη «0».
  • Κάθε λέξη πρέπει να περιέχει τουλάχιστον ένα ψηφίο.

  Αυτό το σύνολο περιγράφει το σύνολο των ακεραίων και είναι υποσύνολο του συνόλου Σ^∗ – είναι λοιπόν γλώσσα πάνω από το αλφάβητο Σ.

• Έστω Σ= {0, 1}. Η κλειστότητα είναι έτσι όλες οι λέξεις που αποτελούνται από μηδενικά και άσους. Μια γλώσσα L πάνω από αυτό το αλφάβητο μπορούμε να την ορίσουμε π.χ. ως το σύνολο όλων των λέξεων που έχουν ακριβώς τρεις άσους. Μπορούμε να είμαστε και πιο δημιουργικοί και να πούμε ότι η γλώσσα L θα είναι το σύνολο όλων των λέξεων που αντιπροσωπεύουν έγκυρη μορφή αρχείου docx (αυτό που βγαίνει από το Word).

• Μένουμε στο δυαδικό αλφάβητο Σ= {0, 1}. Κάθε συμβολοσειρά χαρακτήρων (των συνηθισμένων χαρακτήρων που έχεις στο πληκτρολόγιο) μπορεί να μετατραπεί σε δυαδική μορφή, δηλαδή σε μηδενικά και άσους, και πάλι πίσω, για παράδειγμα με τον πίνακα ASCII (ή ακριβέστερα – ο πίνακας ASCII μετατρέπει χαρακτήρες σε αριθμούς και οι αριθμοί από το δεκαδικό σύστημα μπορούν να μετατραπούν σε αριθμούς στο δυαδικό σύστημα). Έτσι μπορούμε να ορίσουμε τη γλώσσα όλων των λέξεων που αντιστοιχούν σε έγκυρο email και θα εξακολουθεί να είναι γλώσσα πάνω από το δυαδικό αλφάβητο.

Παράθεση γλωσσών: μπορούμε να παραθέσουμε και γλώσσες. Ο ορισμός θα μοιάζει με αυτόν του καρτεσιανού γινομένου συνόλων. Έστω δύο γλώσσες L₁ και L₂. Με την παράθεσή τους L₁ ∘ L₂ παίρνουμε μια νέα γλώσσα, που ορίζεται ως εξής:

$$L_1\circ L_2=\{w_1\circ w_2|w_1\in L_1,w_2\in L_2\}$$

Δηλαδή παίρνουμε όλες τις λέξεις της γλώσσας L₁ και τις παραθέτουμε με όλες τις λέξεις της γλώσσας L₂. Παράδειγμα: έστω

$$\begin{array}{rcl}{L}_1& =& \{0,1\}\\ L_2& =& \{a,b,hi\}\end{array}$$

Τότε ισχύει:

$$\begin{array}{rcl}{L}_1\circ L_2& =& \{0a,0b,0hi,1a,1b,1hi\}\\ L_2\circ L_1& =& \{a0,a1,b0,b1,hi0,hi1\}\\ L_1\circ L_1& =& \{00,01,10,11\}\end{array}$$

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