Τυπική γλώσσα: Διαφορά μεταξύ των αναθεωρήσεων

:''Το άρθρο αυτό αναφέρεται στον όρο '''τυπική γλώσσα''' όπως χρησιμοποιείται στα μαθηματικά, τη λογική και την επιστήμη υπολογιστών. Για πληροφορίες για τον τρόπο έκφρασης που είναι πιο πειθαρχημένος ή ακριβής από την καθημερινή καθομιλουμένη γλώσσα, βλέπε [[επίσημη ορολογία]].''

Στα [[Μαθηματικά]], στην [[Λογική]], και στην [[Επιστήμη Υπολογιστών]], μια '''τυπική γλώσσα''' (formal language) ή απλώς '''γλώσσα''' είναι η γλώσσα που ορίζεται από ακριβείς μαθηματικούς τύπους, ή τύπους που μπορεί να επεξεργαστεί μια μηχανή. Πιό αναλυτικά, μια γλώσσα <math>\boldsymbol{L}</math>ορίζεται ως ένα πιθανώς άπειρο σύνολο από πεπερασμένου μήκους σειρές από στοιχεία που προέρχονται από ένα καθορισμένο πεπερασμένο σύνολο <math>\boldsymbol{A}</math>. Ο κλάδος που μελετά τις ιδιότητες των τυπικών γλωσσών λέγεται θεωρία τυπικών γλωσσών.

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

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

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

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

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

* Στο [[συντακτικό]], που περιγράφει πως ''λέξεις'' στο ''λεξικό'' ή ''λεξιλόγιο'' συνδυάζονται για να δημιουργήσουν ''προτάσεις''.

* Στη [[μορφολογία]], που περιγράφει πως ''μέρη λέξεων'' συνδυάζονται για να δημιουργήσουν ''λέξεις''.

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

* Στη [[φωνολογία]] που περιγράφει πως ''φωνήματα'' συνδυάζονται για να δημιουργήσουν ''λέξεις''.

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

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

* το σύνολο όλων των στοιχειοσειρών που σχηματίζονται από <math>{a, b}</math> <br />

* το σύνολο των συντακτικά σωστών προγραμμάτων σε δεδομένη [[Γλώσσα προγραμματισμού|γλώσσα προγραμματισμού]]

== Πράξεις ==

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

* Η '''[[συμβολοσειρά#συνένωση|συνένωση]]''' (concatenation) <math>L_{1}L_{2}</math> αποτελείται από όλες τις στοιχειοσειρές μορφής <math>vw</math> όπου η <math>v</math> είναι στοιχειοσειρά της <math>L_{1}</math> και η <math>w</math> είναι στοιχειοσειρά της <math>L_{2}</math>.

* Η '''τομή''' (intersection) <math>L_1 \cap L_2</math> των <math>L_{1}</math> και <math>L_{2}</math> αποτελείται από όλες τις στοιχειοσειρές που ανήκουν και στις δύο γλώσσες.

* Η '''ένωση''' (union) <math>L_1 \cup L_2</math> της <math>L_{1}</math> με την <math>L_{2}</math> αποτελείται από όλες τις στοιχειοσειρές που περιέχονται στην <math>L_{1}</math> ή στην <math>L_{2}</math>.

* Το '''συμπλήρωμα''' (complement) της γλώσσας <math>L_{1}</math> αποτελείται από όλες τις στοιχειοσειρές που σχηματίζονται από το αλφάβητο της γλώσσας, αλλά δεν περιέχονται στην <math>L_{1}</math>.

* Το '''δεξιό πηλίκο''' (right quotient) <math>L_{1}/L_{2}</math> της <math>L_{1}</math> δια της <math>L_{2}</math> αποτελείται από όλες τις στοιχειοσειρές <math>v</math> για τις οποίες υπάρχει μια στοιχειοσειρά <math>w</math> στην <math>L_{2}</math> τέτοια ώστε η συναλύσωση <math>vw</math> να περιέχεται στην <math>L_{1}</math>.

* Το '''[[Αστέρι Κλήνυ]]''' (Kleene star) <math>L^{*}</math> αποτελείται από όλες τις στοιχειοσειρές που μπορούν να γραφούν στην μορφή <math>w_{1}w_{2} ... w_{n}</math> , όπου οι στοιχειοσειρές <math>w_{i}</math> περιέχονται στην <math>L</math> και <math>n \ge 0</math>. Ας σημειωθεί ότι περιλαμβάνεται και η κενή στοιχειοσειρά <math>\epsilon</math> επειδή επιτρέπεται το <math>n = 0</math>.

* Το '''αντίστροφο''' <math>L_{1}^{R}</math> περιέχει τις αντίστροφες (παλίνδρομες, καρκινικές) μορφές όλων των στοιχειοσειρών της <math>L_{1}</math>.

* Το '''ανακάτεμα''' των <math>L_{1}</math> και <math>L_{2}</math> απαρτίζεται από όλες τις στοιχειοσειρές που μπορούν να γραφούν στην μορφή <math>v_{1}w_{1}v_{2}w_{2} ... v_{n}w_{n}</math> όπου <math>n \ge 1</math> και οι <math>v_{1}, ... ,v_{n}</math> είναι στοιχειοσειρές που η συναλύσωσή τους <math>v_{1} ... v_{n}</math> περιέχεται στην <math>L_{1}</math> και οι <math>w_{1}, ... ,w_{n}</math> είναι στοιχειοσειρές που η συναλύσωσή τους <math>w_{1} ... w_{n}</math> περιέχεται στην <math>L_{2}</math>.

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

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

== Βλέπε επίσης ==

* [[Συμβολοσειρά| Συμβολοσειρά (string)]]

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

* Χόπκροφτ και Ούλμαν (Hopcroft, J. & Ullman, J), [[1979]] : ''Introduction to Automata Theory, Languages, and Computation.'' (Εισαγωγή στις θεωρίες Αυτομάτων, Γλωσσών, και Υπολογισμών), Addison Wesley, ISBN 020102988X0-201-02988-X

== Αναφορές ==

[[bg:Формален език (математика)]]