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


Στα Μαθηματικά, στην Λογική, και στην Επιστήμη Υπολογιστών, μια τυπική γλώσσα (formal language) ή απλώς γλώσσα είναι η γλώσσα που ορίζεται από ακριβείς μαθηματικούς τύπους, ή τύπους που μπορεί να επεξεργαστεί μια μηχανή. Πιό αναλυτικά, μια γλώσσα ορίζεται ως ένα πιθανώς άπειρο σύνολο από πεπερασμένου μήκους σειρές από στοιχεία που προέρχονται από ένα καθορισμένο πεπερασμένο σύνολο . Ο κλάδος που μελετά τις ιδιότητες των τυπικών γλωσσών λέγεται θεωρία τυπικών γλωσσών.

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

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

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

Ορισμός

Έστω:

* ένα σύνολο ,

* w μια διάταξη με επανατοποθέτηση της μορφής c1c2...cn πεπερασμένου μήκους n, κατασκευασμένη από στοιχεία του συνόλου ,

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

* ένα υποσύνολο .

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

* Το σύνολο είναι μια τυπική γλώσσα.

* Το σύνολο λέγεται το αλφάβητο της γλώσσας.

* Κάθε στοιχείο λέγεται σύμβολο ή χαρακτήρας του αλφαβήτου.

* Κάθε διάταξη πεπερασμένου μήκους λέγεται συμβολοσειρά του αλφαβήτου, και επιπλέον αν τότε λέγεται και λέξη.

Παράδειγμα

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

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

* Κάθε συμβολοσειρά που δεν περιέχει + ή = και δεν αρχίζει με 0 ανήκει στη γλώσσα.

* Η συμβολοσειρά που αποτελείται από το σύμβολο 0 ανήκει στη γλώσσα.

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

* Οποιοσδήποτε αριθμός συμβόλων + μπορούν να υπάρχουν σε μια συμβολοσειρά, αρκεί να περιβάλλονται από σύμβολα διαφορετικά από + και =.

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

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

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

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

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

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

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

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

Προδιαγραφή

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

* Στοιχειοσειρές παραγόμενες από μια Τυπική γραμματική (βλ. Ιεραρχία Τσόμσκι)

* Στοιχειοσειρές παραγόμενες από μια Κανονική έκφραση (regular expression).

* Στοιχειοσειρές που γίνονται αποδεκτές από κάποιο αυτόματο, όπως είναι η Μηχανή Τούρινγκ ή το Μηχανή Πεπερασμένων Καταστάσεων (finite state machine)

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

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

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

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

* το σύνολο όλων των στοιχειοσειρών που σχηματίζονται από a,b



* το σύνολο , όπου n είναι πρώτος αριθμός και an σημαίνει σειρά χαρακτήρων a που είναι n στο πλήθος

w αποτελείται από n πλήθος a, όπου n πρώτος αριθμός

* πεπερασμένες γλώσσες, όπως η

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

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

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

Πράξεις

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

Για παράδειγμα, αν L1 και L2 είναι γλώσσες που ορίζονται πάνω σε ένα κοινό αλφάβητο, τότε:

* Η συναλύσωση (concatenation) L1L2 αποτελείται από όλες τις στοιχειοσειρές μορφής vw όπου η v είναι στοιχειοσειρά της L1 και η w είναι στοιχειοσειρά της L2.

* Η τομή (intersection) των L1 και L2 αποτελείται από όλες τις στοιχειοσειρές που ανήκουν και στις δύο γλώσσες.

* Η ένωση (union) της L1 με την L2 αποτελείται από όλες τις στοιχειοσειρές που περιέχονται στην L1 ή στην L2.

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

* Το δεξιό πηλίκο (right quotient) L1 / L2 της L1 δια της L2 αποτελείται από όλες τις στοιχειοσειρές v για τις οποίες υπάρχει μια στοιχειοσειρά w στην L2 τέτοια ώστε η συναλύσωση vw να περιέχεται στην L1.

* Το Αστέρι Κλήνυ (Kleene star) L * αποτελείται από όλες τις στοιχειοσειρές που μπορούν να γραφούν στην μορφή w1w2...wn , όπου οι στοιχειοσειρές wi περιέχονται στην L και . Ας σημειωθεί ότι περιλαμβάνεται και η κενή στοιχειοσειρά ε επειδή επιτρέπεται το n = 0.

* Το αντίστροφο περιέχει τις αντίστροφες (παλίνδρομες, καρκινικές) μορφές όλων των στοιχειοσειρών της L1.

* Το ανακάτεμα των L1 και L2 απαρτίζεται από όλες τις στοιχειοσειρές που μπορούν να γραφούν στην μορφή v1w1v2w2...vnwn όπου και οι v1,...,vn είναι στοιχειοσειρές που η συναλύσωσή τους v1...vn περιέχεται στην L1 και οι w1,...,wn είναι στοιχειοσειρές που η συναλύσωσή τους w1...wn περιέχεται στην L2.

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

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

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

* Για το άρθρο αντλήθηκαν πληροφορίες και από το άρθρο w:en:Formal_language της αγγλικής Βικιπαίδειας.

Βλέπε επίσης

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

* Αλφάβητο

* Κανονικές εκφράσεις (regular expressions)

* Γλώσσα προγραμματισμού για εφαρμογές τυπικών γλωσσών σε προγραμματισμό υπολογιστών

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

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

* Ρόζενμπεργκ και Σαλόμα (G. Rozenberg, A. Salomaa eds.), Handbook of Formal Languages (Εγχειρίδιο Τυπικών Γλωσσών), Springer-Verlag, (3 τόμοι)

* 33η Διεθνής Συνάντηση (Colloquium) ICALP 2006 για Αυτόματα, Γλώσσες και Προγραμματισμό

* 10ο Διεθνές Συνέδριο (Conference) DLT 2006 για εξελίξεις στην Θεωρία Γλωσσών

Εικόνα:Mathepag.jpg

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

Μαθηματικά

Από τη ελληνική Βικιπαίδεια http://el.wikipedia.org . Όλα τα κείμενα είναι διαθέσιμα υπό την GNU Free Documentation License

<@=@=@>


www.hellenica.de