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

 

Στα διακριτά μαθηματικά, στη μαθηματική λογική και στη θεωρητική πληροφορική, μια τυπική γλώσσα (formal language) ή απλώς γλώσσα είναι η γλώσσα που ορίζεται από ακριβείς μαθηματικούς τύπους, ή τύπους που μπορεί να επεξεργαστεί μια μηχανή. Πιο αναλυτικά, μια γλώσσα \( {\displaystyle {\boldsymbol {L}}} \) ορίζεται ως ένα πιθανώς άπειρο σύνολο από πεπερασμένου μήκους σειρές από στοιχεία προερχόμενα από ένα καθορισμένο, πεπερασμένο σύνολο \( {\displaystyle {\boldsymbol {A}}} \) (αλφάβητο). Ο κλάδος που μελετά τις ιδιότητες των τυπικών γλωσσών λέγεται θεωρία τυπικών γλωσσών.

Όπως και οι γλώσσες στη γλωσσολογία, οι τυπικές γλώσσες έχουν γενικά δυο πλευρές:

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

Ορισμός

Έστω:

ένα σύνολο \( {\displaystyle {\boldsymbol {A}}} \),
\( {\displaystyle w} \)μια διάταξη με επανατοποθέτηση της μορφής \({\displaystyle c_{1}c_{2}...c_{n}} \) πεπερασμένου μήκους n, κατασκευασμένη από στοιχεία \( {\displaystyle c_{1},...,c_{n}\in {\boldsymbol {A}}} \) του συνόλου \({\displaystyle {\boldsymbol {A}}} \),
το σύνολο \( {\displaystyle {\boldsymbol {A}}^{*}} \) όλων των δυνατών διατάξεων στοιχείων του \({\displaystyle {\boldsymbol {A}}} \) που έχουν πεπερασμένο μήκος, και
ένα υποσύνολο \( {\displaystyle {\boldsymbol {L}}\in {\boldsymbol {A}}^{*}} \).

Τότε ορίζουμε ότι:

Το σύνολο \( {\displaystyle {\boldsymbol {L}}} \) είναι μια τυπική γλώσσα.
Το σύνολο \( {\displaystyle {\boldsymbol {A}}} \) λέγεται το αλφάβητο της γλώσσας.
Κάθε στοιχείο \( {\displaystyle c\in {\boldsymbol {A}}} \) λέγεται σύμβολο ή χαρακτήρας του αλφαβήτου.
Κάθε διάταξη πεπερασμένου μήκους \({\displaystyle w\in {\boldsymbol {A}}^{*}} \) λέγεται συμβολοσειρά του αλφαβήτου, και επιπλέον αν \( {\displaystyle w\in {\boldsymbol {L}}} \) τότε λέγεται και λέξη.

Παράδειγμα

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

Θεωρήστε ένα απλό παράδειγμα, το αλφάβητο {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, =}, και τους ακόλουθους συντακτικούς κανόνες:

• Κάθε συμβολοσειρά που δεν περιέχει + ή = και δεν αρχίζει με 0 ανήκει στη γλώσσα.
• Η συμβολοσειρά που αποτελείται από το σύμβολο 0 ανήκει στη γλώσσα.
• Μια συμβολοσειρά που περιέχει το = ανήκει στη γλώσσα, αν και μόνον αν υπάρχει ακριβώς ένα = το οποίο τη χωρίζει σε δυο συμβολοσειρές, που ανήκουν στη γλώσσα.
• Οποιοσδήποτε αριθμός συμβόλων + μπορούν να υπάρχουν σε μια συμβολοσειρά, αρκεί να περιβάλλονται από σύμβολα διαφορετικά από + και =.
• Δεν ανήκουν άλλες συμβολοσειρές στη γλώσσα εκτός από αυτές που ικανοποιούν τους παραπάνω κανόνες.

Υπό αυτούς τους κανόνες, η συμβολοσειρά "23+4=555" ανήκει στη γλώσσα, ενώ η συμβολοσειρά "-234=+" δεν ανήκει. Η τυπική γλώσσα αυτή περιγράφει αριθμούς, καλώς ορισμένες εκφράσεις πρόσθεσης, και καλώς ορισμένες εξισώσεις προσθέσεων, αλλά εκφράζει μόνο το πως φαίνονται (το συντακτικό τους), και όχι το τι σημαίνουν (τη σημασιολογία ή σημαντική τους). Για παράδειγμα, δεν ορίζεται πουθενά στους παραπάνω κανόνες ότι το σύμβολο 0 σημαίνει τον αριθμό μηδέν ή ότι το σύμβολο + σημαίνει πρόσθεση.

Θεωρία τυπικών γλωσσών

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

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

Προδιαγραφή

Μια τυπική γλώσσα μπορεί να προδιαγραφεί με αρκετούς διαφορετικούς τρόπους, όπως:

Συμβολοσειρές παραγόμενες από μια τυπική γραμματική (βλ. Ιεραρχία Τσόμσκι).
Συμβολοσειρές παραγόμενες από μια κανονική έκφραση (regular expression).
Συμβολοσειρές που γίνονται αποδεκτές από κάποιο αυτόματο, όπως είναι μία Μηχανή Τούρινγκ ή μία μηχανή πεπερασμένων καταστάσεων (finite state machine).
Από ένα σύνολο σχετιζομένων λογικών ερωτήσεων, εκείνες οι ερωτήσεις που έχουν απάντηση ΑΛΗΘΗΣ (βλ. Πρόβλημα απόφασης).

Πράξεις

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

Για παράδειγμα, αν \( {\displaystyle L_{1}} \) και \( {\displaystyle L_{2}} \) είναι γλώσσες που ορίζονται πάνω σε ένα κοινό αλφάβητο, τότε:

Η συνένωση (concatenation) \( {\displaystyle L_{1}L_{2}}\) αποτελείται από όλες τις συμβολοσειρές μορφής \( {\displaystyle vw} \) όπου η \( {\displaystyle v} \) είναι συμβολοσειρά της \( {\displaystyle L_{1}} \) και η \( {\displaystyle w} \) είναι συμβολοσειρά της \( {\displaystyle L_{2}} \) .
Η τομή (intersection) \( {\displaystyle L_{1}\cap L_{2}} \) των \( {\displaystyle L_{1}} \) και \( {\displaystyle L_{2}} \) αποτελείται από όλες τις συμβολοσειρές που ανήκουν και στις δύο γλώσσες.
Η ένωση (union) \( {\displaystyle L_{1}\cup L_{2}} \) της \( {\displaystyle L_{1}}\) με την \( {\displaystyle L_{2}} \) αποτελείται από όλες τις συμβολοσειρές που περιέχονται στην \( {\displaystyle L_{1}} \) ή στην \( {\displaystyle L_{2}} \) .
Το συμπλήρωμα (complement) της γλώσσας \( {\displaystyle L_{1}} \) αποτελείται από όλες τις συμβολοσειρές που σχηματίζονται από το αλφάβητο της γλώσσας, αλλά δεν περιέχονται στην \( {\displaystyle L_{1}} \).
Το δεξιό πηλίκο (right quotient) L\( {\displaystyle L_{1}/L_{2}} \) της \( {\displaystyle L_{1}} \) δια της \( {\displaystyle L_{2}} \) } αποτελείται από όλες τις συμβολοσειρές \( {\displaystyle v} \) για τις οποίες υπάρχει μια συμβολοσειρά \( {\displaystyle w} \) στην \( {\displaystyle L_{2}}\) τέτοια ώστε η συνένωση \( {\displaystyle vw} \) να περιέχεται στην \( {\displaystyle L_{1}} \).
Το Άστρο του Κλήνυ (Kleene star) \( {\displaystyle L^{*}} \) αποτελείται από όλες τις συμβολοσειρές που μπορούν να γραφούν στην μορφή \( {\displaystyle w_{1}w_{2}...w_{n}} \), όπου οι συμβολοσειρές \( i {\displaystyle w_{i}} \) περιέχονται στην \( {\displaystyle L} \) και \( {\displaystyle n\geq 0} \) . Περιλαμβάνεται και η κενή συμβολοσειρά \( {\displaystyle \epsilon }\) επειδή επιτρέπεται το \( {\displaystyle n=0} \).
Το αντίστροφο \( {\displaystyle L_{1}^{R}} \) περιέχει τις αντίστροφες (παλίνδρομες, καρκινικές) μορφές όλων των συμβολοσειρών της \( {\displaystyle L_{1}} \).
Το ανακάτεμα των \( {\displaystyle L_{1}} \) και \( {\displaystyle L_{2}} \) απαρτίζεται από όλες τις συμβολοσειρές που μπορούν να γραφούν στην μορφή \( {\displaystyle v_{1}w_{1}v_{2}w_{2}...v_{n}w_{n}} \) όπου \( {\displaystyle n\geq 1} \) και οι \( {\displaystyle v_{1},...,v_{n}}\) είναι συμβολοσειρές που η συνένωσή τους τους\( {\displaystyle v_{1}...v_{n}} \) περιέχεται στην \( {\displaystyle L_{1}} \) και οι \( {\displaystyle w_{1},...,w_{n}} \) είναι συμβολοσειρές που η συνένωσή τους \( {\displaystyle w_{1}...w_{n}} \) περιέχεται στην\( {\displaystyle L_{2}} \).

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

Βιβλιογραφία

H.R. Lewis, C.H. Papadimitriou, Elements of the Theory of Computation, Prentice Hall, 2nd Edition

Δείτε επίσης

Αλφάβητο
Γλώσσα προγραμματισμού για εφαρμογές τυπικών γλωσσών σε προγραμματισμό υπολογιστών
Κανονικές εκφράσεις (regular expressions)
Τυπική σημασιολογία
Συμβολοσειρά (string)

Περαιτέρω διάβασμα

Χόπκροφτ και Ούλμαν (Hopcroft, J. & Ullman, J), 1979 : Introduction to Automata Theory, Languages, and Computation. (Εισαγωγή στις θεωρίες Αυτομάτων, Γλωσσών, και Υπολογισμών), Addison Wesley, ISBN 0-201-02988-X
Ρόζενμπεργκ και Σαλόμα (G. Rozenberg, A. Salomaa eds.), Handbook of Formal Languages (Εγχειρίδιο Τυπικών Γλωσσών), Springer-Verlag, (3 τόμοι)
33η Διεθνής Συνάντηση (Colloquium) ICALP 2006 για Αυτόματα, Γλώσσες και Προγραμματισμό
10ο Διεθνές Συνέδριο (Conference) DLT 2006 για εξελίξεις στην Θεωρία Γλωσσών

Θεωρία αυτομάτων: τυπικές γλώσσες και τυπικές γραμματικές
Ιεραρχία Τσόμσκι Γραμματικές Γλώσσες Ελάχιστο
αυτόματο
Τύπος-0 Απεριόριστες Αναδρομικά αριθμήσιμη Μηχανή Τούρινγκ
- (χωρίς κοινό όνομα) Αναδρομική Αποφασιστής
Τύπος-1 Με συμφραζόμενα Με συμφραζόμενα Γραμμικό φραγμένο
Τύπος-2 Χωρίς συμφραζόμενα Χωρίς συμφραζόμενα Σωρού
Τύπος-3 Κανονική Κανονική Πεπερασμένο
Κάθε κατηγορία γλώσσας ή γραμματικής είναι γνήσιο υποσύνολο της κατηγορίας που είναι ακριβώς από πάνω της.
Αναφορές

Στο λήμμα αυτό έχει ενσωματωθεί κείμενο από το λήμμα Formal language της Αγγλικής Βικιπαίδειας, η οποία διανέμεται υπό την GNU FDL και την CC-BY-SA 3.0. (ιστορικό/συντάκτες).