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

Στα διακριτά μαθηματικά, στη μαθηματική λογική, στη θεωρητική πληροφορική και στη γλωσσολογία, μια **τυπική γλώσσα** (formal language) ή απλώς **γλώσσα** είναι η γλώσσα που ορίζεται από ακριβείς μαθηματικούς τύπους, ή τύπους που μπορεί να επεξεργαστεί μια μηχανή. Πιο αναλυτικά, μια γλώσσα WIKINIUM\_MATH\_PH\_0 ορίζεται ως ένα πιθανώς άπειρο σύνολο από πεπερασμένου μήκους σειρές από στοιχεία προερχόμενα από ένα καθορισμένο, πεπερασμένο σύνολο WIKINIUM\_MATH\_PH\_2 (αλφάβητο). Ο κλάδος που μελετά τις ιδιότητες των τυπικών γλωσσών λέγεται **θεωρία τυπικών γλωσσών**.

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

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

## Ορισμός

Έστω:

* ένα σύνολο WIKINIUM\_MATH\_PH\_4 ,
* WIKINIUM\_MATH\_PH\_6 μια διάταξη με επανατοποθέτηση της μορφής WIKINIUM\_MATH\_PH\_8 πεπερασμένου μήκους WIKINIUM\_MATH\_PH\_10 , κατασκευασμένη από στοιχεία WIKINIUM\_MATH\_PH\_12 του συνόλου WIKINIUM\_MATH\_PH\_14 ,
* το σύνολο WIKINIUM\_MATH\_PH\_16 όλων των δυνατών διατάξεων στοιχείων του WIKINIUM\_MATH\_PH\_18 που έχουν πεπερασμένο μήκος, και
* ένα υποσύνολο WIKINIUM\_MATH\_PH\_20 .

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

* Το σύνολο WIKINIUM\_MATH\_PH\_22 είναι μια **τυπική γλώσσα**.
* Το σύνολο WIKINIUM\_MATH\_PH\_24 λέγεται το **αλφάβητο** της γλώσσας.
* Κάθε στοιχείο WIKINIUM\_MATH\_PH\_26 λέγεται **σύμβολο** ή **χαρακτήρας** του αλφαβήτου.
* Κάθε διάταξη πεπερασμένου μήκους WIKINIUM\_MATH\_PH\_28 λέγεται **συμβολοσειρά** του αλφαβήτου, και επιπλέον αν WIKINIUM\_MATH\_PH\_30 τότε λέγεται και **λέξη**.

## Παράδειγμα

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

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

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

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

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

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

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

## Προδιαγραφή

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

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

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

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

Το αλφάβητο έστω ότι είναι το WIKINIUM\_MATH\_PH\_32 . Παραδείγματα γλωσσών τότε είναι:

* το σύνολο όλων των συμβολοσειρών που σχηματίζονται από WIKINIUM\_MATH\_PH\_34

 WIKINIUM\_MATH\_PH\_36
* το σύνολο WIKINIUM\_MATH\_PH\_38 , όπου n είναι πρώτος αριθμός και WIKINIUM\_MATH\_PH\_40 σημαίνει σειρά χαρακτήρων WIKINIUM\_MATH\_PH\_42 που είναι WIKINIUM\_MATH\_PH\_44 στο πλήθος

 WIKINIUM\_MATH\_PH\_46 w αποτελείται από WIKINIUM\_MATH\_PH\_48 πλήθος WIKINIUM\_MATH\_PH\_50 , όπου WIKINIUM\_MATH\_PH\_52 πρώτος αριθμός WIKINIUM\_MATH\_PH\_54
* πεπερασμένες γλώσσες, όπως η WIKINIUM\_MATH\_PH\_56

ή επίσης γενικότερα παραδείγματα:

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

## Πράξεις

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

Για παράδειγμα, αν WIKINIUM\_MATH\_PH\_58 και WIKINIUM\_MATH\_PH\_60 είναι γλώσσες που ορίζονται πάνω σε ένα κοινό αλφάβητο, τότε:

* Η **συνένωση** (concatenation) WIKINIUM\_MATH\_PH\_62 αποτελείται από όλες τις συμβολοσειρές μορφής WIKINIUM\_MATH\_PH\_64 όπου η WIKINIUM\_MATH\_PH\_66 είναι συμβολοσειρά της WIKINIUM\_MATH\_PH\_68 και η WIKINIUM\_MATH\_PH\_70 είναι συμβολοσειρά της WIKINIUM\_MATH\_PH\_72 .
* Η **τομή** (intersection) WIKINIUM\_MATH\_PH\_74 των WIKINIUM\_MATH\_PH\_76 και WIKINIUM\_MATH\_PH\_78 αποτελείται από όλες τις συμβολοσειρές που ανήκουν και στις δύο γλώσσες.
* Η **ένωση** (union) WIKINIUM\_MATH\_PH\_80 της WIKINIUM\_MATH\_PH\_82 με την WIKINIUM\_MATH\_PH\_84 αποτελείται από όλες τις συμβολοσειρές που περιέχονται στην WIKINIUM\_MATH\_PH\_86 ή στην WIKINIUM\_MATH\_PH\_88 .
* Το **συμπλήρωμα** (complement) της γλώσσας WIKINIUM\_MATH\_PH\_90 αποτελείται από όλες τις συμβολοσειρές που σχηματίζονται από το αλφάβητο της γλώσσας, αλλά δεν περιέχονται στην WIKINIUM\_MATH\_PH\_92 .
* Το **δεξιό πηλίκο** (right quotient) WIKINIUM\_MATH\_PH\_94 της WIKINIUM\_MATH\_PH\_96 δια της WIKINIUM\_MATH\_PH\_98 αποτελείται από όλες τις συμβολοσειρές WIKINIUM\_MATH\_PH\_100 για τις οποίες υπάρχει μια συμβολοσειρά WIKINIUM\_MATH\_PH\_102 στην WIKINIUM\_MATH\_PH\_104 τέτοια ώστε η συνένωση WIKINIUM\_MATH\_PH\_106 να περιέχεται στην WIKINIUM\_MATH\_PH\_108 .
* Το **Άστρο του Κλήνυ** (Kleene star) WIKINIUM\_MATH\_PH\_110 αποτελείται από όλες τις συμβολοσειρές που μπορούν να γραφούν στην μορφή WIKINIUM\_MATH\_PH\_112 , όπου οι συμβολοσειρές WIKINIUM\_MATH\_PH\_114 περιέχονται στην WIKINIUM\_MATH\_PH\_116 και WIKINIUM\_MATH\_PH\_118 . Περιλαμβάνεται και η κενή συμβολοσειρά WIKINIUM\_MATH\_PH\_120 επειδή επιτρέπεται το WIKINIUM\_MATH\_PH\_122 .
* Το **αντίστροφο** WIKINIUM\_MATH\_PH\_124 περιέχει τις αντίστροφες (παλίνδρομες, καρκινικές) μορφές όλων των συμβολοσειρών της WIKINIUM\_MATH\_PH\_126 .
* Το **ανακάτεμα** των WIKINIUM\_MATH\_PH\_128 και WIKINIUM\_MATH\_PH\_130 απαρτίζεται από όλες τις συμβολοσειρές που μπορούν να γραφούν στην μορφή WIKINIUM\_MATH\_PH\_132 όπου WIKINIUM\_MATH\_PH\_134 και οι WIKINIUM\_MATH\_PH\_136 είναι συμβολοσειρές που η συνένωσή τους τους WIKINIUM\_MATH\_PH\_138 περιέχεται στην WIKINIUM\_MATH\_PH\_140 και οι WIKINIUM\_MATH\_PH\_142 είναι συμβολοσειρές που η συνένωσή τους WIKINIUM\_MATH\_PH\_144 περιέχεται στην WIKINIUM\_MATH\_PH\_146 .

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

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

* 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 Αρχειοθετήθηκε 2006-06-09 στο Wayback Machine. για Αυτόματα, Γλώσσες και Προγραμματισμό
* 10ο Διεθνές Συνέδριο (Conference) DLT 2006 για εξελίξεις στην Θεωρία Γλωσσών

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

## Εξωτερικοί σύνδεσμοι

* Πολυμέσα σχετικά με το θέμα  Τυπική γλώσσα στο Wikimedia Commons