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

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

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

Το αλφάβητο έστω ότι είναι το $\left \{ a , b \right \}$ .

Μια στοιχειοσειρά φτιαγμένη με αυτό το αλφάβητο είναι, για παράδειγμα, η $a b a b b a$ .

Μια τυπική γλώσσα φτιαγμένη με αυτό το αλφάβητο, και που να περιέχει αυτή την στοιχειοσειρά, θα μπορούσε να είναι το σύνολο όλων των στοιχειοσειρών που περιέχουν τόσα σύμβολα $a$ όσα και $b$ .

Η κενή λέξη (δηλαδή η στοιχειοσειρά με μήκος μηδενικό) επιτρέπεται και συμβολίζεται συχνά με $e$ , $ε$ ή $Λ$ .

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

Το πιο συνηθισμένο ερώτημα σχετικό με τις τυπικές γλώσσες είναι "πόσο δύσκολο είναι να αποφανθούμε αν μια δεδομένη λέξη ανήκει στην γλώσσα; " και είναι αντικείμενο της θεωρίας υπολογισιμότητας (computability theory) και της θεωρίας πολυπλοκότητας (complexity theory).

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

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

[Επεξεργασία] Προδιαγραφή

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

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

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

Αρκετές πράξεις μπορούν να εφαρμοσθούν για να παραχθούν νέες γλώσσες από δεδομένες γλώσσες.

Υποθέτουμε στα επόμενα ότι $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$ αποτελείται από όλες τις στοιχειοσειρές της $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_{1}^{*}$ αποτελείται από όλες τις στοιχειοσειρές που μπορούν να γραφούν στην μορφή $w 1 w 2 ... w n$ , όπου οι στοιχειοσειρές $w i$ περιέχονται στην $L 1$ και $n \ge 0$ . Ας σημειωθεί ότι περιλαμβάνεται και η κενή στοιχειοσειρά $ε$ επειδή επιτρέπεται το $n = 0$ .

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

Το αντίστροφο (reverse) $L_{1}^{R}$ περιέχει τις αντίστροφες (παλίνδρομες, καρκινικές) μορφές όλων των στοιχειοσειρών της $L 1$ .

[Επεξεργασία] Ανακάτεμα

Το ανακάτεμα (shuffle) των $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$ .

[Επεξεργασία] Δείτε επίσης

Γλώσσα για γλώσσες γενικά
Σύνταξη για την μορφή μιας γλώσσας γενικά
Σημασιολογία για τις έννοιες σε μια γλώσσα
Φυσική γλώσσα για γλώσσες που δεν είναι τυπικές
Γλώσσα υπολογιστική για εφαρμογές τυπικών γλωσσών σε υπολογιστές
Γλώσσα προγραμματισμού για εφαρμογές τυπικών γλωσσών σε προγραμματισμό υπολογιστών

[Επεξεργασία] Περαιτέρω διάβασμα

Χόπκροφτ και Ούλμαν (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 για εξελίξεις στην Θεωρία Γλωσσών

[Επεξεργασία] Πηγές

Το άρθρο είναι μεταφορά στα ελληνικά του άρθρου w:en:Formal_language της αγγλικής Βικιπαίδειας.

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

Ανακτήθηκε από "http://el.wikipedia.org../../../%CF%84/%CF%85/%CF%80/%CE%A4%CF%85%CF%80%CE%B9%CE%BA%CE%AE_%CE%B3%CE%BB%CF%8E%CF%83%CF%83%CE%B1.html"

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