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

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια

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

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

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

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

[Επεξεργασία] Ορισμός

Έστω:

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

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

Το σύνολο $\boldsymbol{L}$ είναι μια τυπική γλώσσα.
Το σύνολο $\boldsymbol{A}$ λέγεται το αλφάβητο της γλώσσας.
Κάθε στοιχείο $c \in \boldsymbol{A}$ λέγεται σύμβολο ή χαρακτήρας του αλφαβήτου.
Κάθε διάταξη πεπερασμένου μήκους $w \in \boldsymbol{A}^*$ λέγεται συμβολοσειρά του αλφαβήτου, και επιπλέον αν $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)
Από ένα σύνολο σχετιζομένων λογικών ερωτήσεων, εκείνες οι ερωτήσεις που έχουν απάντηση ΑΛΗΘΗΣ (βλ. Πρόβλημα απόφασης).

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

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

Το αλφάβητο έστω ότι είναι το $\left \{ a , b \right \}$ . Παραδείγματα γλωσσών τότε είναι:

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

$L = \{ w \in \Sigma^*\ \}$

το σύνολο $\left \{ a^{n}\right\}$ , όπου n είναι πρώτος αριθμός και $a n$ σημαίνει σειρά χαρακτήρων $a$ που είναι $n$ στο πλήθος

$L = \{ w \in \Sigma^*\ \colon$ w αποτελείται από

n

πλήθος

a

, όπου

n

πρώτος αριθμός $\ \}$

πεπερασμένες γλώσσες, όπως η $L = \{a,\ aa,\ bba \}$

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

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

[Επεξεργασία] Πράξεις

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

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

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

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

[Επεξεργασία] Βιβλιογραφία

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 για εξελίξεις στην Θεωρία Γλωσσών

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

[Επεξεργασία] Αναφορές

Το άρθρο αντλεί πληροφορίες από το αντίστοιχο της αγγλόφωνης Wikipedia.

Κατηγορίες: Τυπικές γλώσσες | Μαθηματική λογική

See also ebooksgratis.com: no banners, no cookies, totally FREE.