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

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

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

Ένα νήμα φτιαγμένο με αυτό το αλφάβητο είναι, για παράδειγμα, το $ababba$ .

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

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

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

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

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

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

Προδιαγραφή

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

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

Πράξεις

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

L_{1}

και

L_{2}

είναι γλώσσες με το ίδιο αλφάβητο.

Η συναλύσωση (concatenation) $L_{1}L_{2}$ αποτελείται από όλα τα νήματα μορφής $vw$ όπου το $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}$ τέτοιο ώστε το $vw$ να περιέχεται στην $L_{1}$ .
Το Αστέρι Κλέινι (Kleene star) $L_{1}^{*}$ αποτελείται από όλα τα νήματα που μπορούν να γραφούν στην μορφή $w_{1}w_{2} ... w_{n}$ , όπου τα νήματα $w_{i}$ περιέχονται στην $L_{1}$ και $n \ge 0$ . Ας σημειωθεί ότι περιλαμβάνεται και το κενό νήμα $\epsilon$ επειδή επιτρέπεται το $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 για εξελίξεις στην Θεωρία Γλωσσών

Πηγές

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

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