Langue formelle

Un langage formel est un langage abstrait dans lequel, contrairement aux langages naturels, ce n'est souvent pas la communication qui est au premier plan, mais l'usage mathématique. Un langage formel est constitué d'un certain nombre de chaînes de symboles (généralement des chaînes de caractères ) («mots» de la langue), qui peuvent être assemblées à partir d'un ensemble de caractères / symboles («alphabet», symboles de base). Les langages formels sont utilisés en linguistique , en logique et en informatique théorique .

Les langages formels conviennent pour la description (mathématiquement) précise de la gestion des chaînes de caractères. Par exemple, des formats de données ou des langages de programmation entiers peuvent être spécifiés. Avec la sémantique formelle , les chaînes de caractères définies reçoivent une signification (mathématique). Dans un langage de programmation, une instruction de programmation (dans le cadre du langage formel) peut se voir attribuer un comportement machine unique (dans le cadre de la sémantique ).

Sur la base de langages formels, cependant, des calculs logiques peuvent également être définis avec lesquels des conclusions mathématiques peuvent être tirées. En relation avec les langages de programmation définis formellement, les calculs peuvent aider à vérifier l' exactitude des programmes .

définition

Un langage formel sur un alphabet est un sous - ensemble de shell ash de trèfle de l'alphabet: . ${\ displaystyle L}$${\ displaystyle \ Sigma}$${\ displaystyle L \ subseteq \ Sigma ^ {*}}$

Un alphabet définit les caractères à partir desquels un " mot " de la langue peut être formé. Par exemple, vous pouvez créer la représentation décimale de n'importe quel nombre naturel de l'alphabet . ${\ displaystyle \ Sigma}$${\ displaystyle \ Sigma = \ {0,1,2,3,4,5,6,7,8,9 \}}$

Tous les mots de longueur finie (longueur 0 ou plus) qui peuvent être arbitrairement formés à partir d'un alphabet donné et dont chaque lettre individuelle est un élément de , ce plus grand nombre de mots possible pour l'alphabet , est appelé la coquille de Kleen de l'alphabet. , en bref . Un langage formel sur un alphabet est donc un certain sous - ensemble de la coquille Kleene de votre alphabet - en général, pas toutes les combinaisons de caractères arbitraires est un mot valide dans la langue. ${\ displaystyle \ Sigma}$${\ displaystyle \ Sigma}$${\ displaystyle \ Sigma}$${\ displaystyle \ Sigma}$${\ displaystyle \ Sigma ^ {*}}$${\ displaystyle \ Sigma}$

Les langues formelles peuvent être vides, finies ou infinies; tout au plus peuvent-ils englober toute la coquille Kleenesche de leur alphabet. Ils peuvent être définis par une condition mathématique sur leurs mots: "La langue ... est l'ensemble de tous les mots pour lesquels ..." s'applique.

Cependant, les langues utilisées en informatique théorique sont généralement définies plus spécifiquement par une certaine procédure de remplacement - des règles sur la manière dont les caractères de l'alphabet sont / peuvent être combinés. Il existe différents types de méthodes de remplacement: les systèmes Semi-Thue , les grammaires Chomsky , les systèmes Lindenmayer et autres. De tels processus de remplacement sont basés, par exemple, sur une chaîne de caractères de début spécifique, qui est progressivement convertie en structures de mots par l'application répétée («récursive») des règles (remplacements de texte), qui alors dans leur ensemble, ou seulement une section spécifiée tel que les mots s’appliquent à la langue. On parle aussi ici de grammaires génératives , car les mots d'une langue sont générés pas à pas via de telles substitutions de texte . Inversement, les langues peuvent également être définies comme l'ensemble de tous les mots à partir desquels un certain mot prédéfini ou l'un de plusieurs mots prédéfinis peut être généré (via le processus de remplacement de langue). ("Tout appartient à un langage qui peut être retracé ... à travers les règles.")

Différenciation des langues naturelles

A l'aide de langages formels, les langages naturels peuvent également être modélisés, en particulier leur syntaxe. Cependant, lors de la comparaison des langues formelles avec les langues naturelles, il convient de noter que les langues naturelles ont au moins les deux niveaux hiérarchiques superposés du mot et de la phrase au-dessus des signes phonétiques élémentaires . Les règles de leur structure sont généralement divisées en morphologie d'une part et syntaxe d'autre part. Dans les langages formels, en revanche, il n'y a souvent qu'un seul niveau de la hiérarchie du mot formel au-dessus du signe élémentaire de l'alphabet ; en termes de structure des mots, on parle de syntaxe. Si une langue naturelle est modélisée en utilisant une langue formelle, les phrases de la langue naturelle sont appelées des mots d'un point de vue formel .

De plus, les énoncés en langage naturel ont une signification naturelle, tandis que le sens des langages formels doit toujours être défini de manière formelle.

Exemples

1. Le langage de programmation C est un langage formel. Les mots de C sont les programmes respectifs. L'alphabet de C sont les mots - clés et les caractères définis dans la définition de C.
2. Les nombres naturels en représentation unaire: ${\ displaystyle \ mathbb {N} _ {\ rm {un}}: = \ {\ varepsilon, 1,11,111,1111, \ ldots \}}$
3. Le langage unaire ci - dessus , qui ne contient que des mots de longueur carrée:${\ displaystyle \ {a \}}$${\ displaystyle {\ rm {quad \ _count}}: = \ {a ^ {(n ^ {2})} \ mid n \ in \ mathbb {N} \}}$
4. ${\ displaystyle {\ rm {count}} _ {2}: = \ {a ^ {n} b ^ {n} \ mid n \ in \ mathbb {N} \}}$
5. ${\ displaystyle {\ rm {count}} _ {3}: = \ {a ^ {n} b ^ {n} c ^ {n} \ mid n \ in \ mathbb {N} \}}$
6. La langue de tous les palindromes : , où la réflexion du mot est.${\ displaystyle {\ rm {pal}}: = \ {w \ in \ {0.1 \} ^ {*} \ mid w = w ^ {R} \}}$
   ${\ displaystyle w ^ {R}}$${\ displaystyle w}$
7. La décimale de codage des nombres premiers: . Ici, le codage des nombres naturels dénote dans le système décimal et PRIM représente l'ensemble des nombres premiers .${\ displaystyle {\ rm {prim}} _ {\ rm {dec}}: = \ {{\ rm {dec}} (p) \ mid p \ in {\ rm {PRIM}} \}}$
   ${\ displaystyle {\ rm {dec}} \ colon \ mathbb {N} \ rightarrow \ {0,1,2,3,4,5,6,7,8,9 \} ^ {*}}$
8. Le Morse ou séquence Thue : , dans lequel un morphisme est défini comme suit: et , . Ainsi les premiers éléments de la séquence Thue sont: 0, 01, 0110, 01101001, 0110100110010110 ...${\ displaystyle {\ rm {thue}}: = \ {h_ {t} ^ {n} (0) \ mid n \ in \ mathbb {N} \}}$
   ${\ displaystyle h_ {t}}$${\ displaystyle h_ {t} (\ varepsilon) = \ varepsilon}$${\ displaystyle h_ {t} (w0): = h_ {t} (w) 01}$${\ displaystyle h_ {t} (w1): = h_ {t} (w) 10}$
   

Opérations sur les langues formelles

Deux langues au-dessus de l'alphabet et au-dessus de l'alphabet sont banales, les deux langues sont également au - dessus , c'est-à-dire des ensembles de mots . Par conséquent sont également ${\ displaystyle L_ {1}}$${\ displaystyle \ Sigma _ {1}}$${\ displaystyle L_ {2}}$${\ displaystyle \ Sigma _ {2}}$${\ displaystyle \ Sigma _ {1} \ cup \ Sigma _ {2}}$${\ displaystyle (\ Sigma _ {1} \ cup \ Sigma _ {2}) ^ {*}}$

• le syndicat ${\ displaystyle L_ {1} \ cup L_ {2}}$
• la moyenne ${\ displaystyle L_ {1} \ cap L_ {2}}$
• la différence ${\ displaystyle L_ {1} \ setminus L_ {2}}$

Langues sur . ${\ displaystyle \ Sigma _ {1} \ cup \ Sigma _ {2}}$

D'autres opérations sur les langues sont:

Enchaînement

La concaténation de deux langues et est la langue des mots qui est créée en écrivant un mot après l'autre ( concaténation ) de et de : ${\ displaystyle L_ {1}}$${\ displaystyle L_ {2}}$${\ displaystyle u}$${\ displaystyle L_ {1}}$${\ displaystyle v}$${\ displaystyle L_ {2}}$

${\ displaystyle L_ {1} \ circ L_ {2}: = \ {uv \ mid u \ in L_ {1}, v \ in L_ {2} \}}$.

Par exemple, les concaténations de différentes langues au-dessus de l'alphabet sont : ${\ displaystyle \ Sigma = \ {a, \, b \}}$

${\ displaystyle \ {a \} \ circ \ {ab \} = \ {aab \}}$

${\ displaystyle \ {a, \, bb \} \ circ \ {aa, \, b \} = \ {aaa, \, ab, \, bbaa, \, bbb \}}$

${\ displaystyle \ {abb, \, bab \} \ circ \ {\ varepsilon, \, aab, \, bb \} = \ {abb, \, bab, \, abbaab, \, babaab, \, abbbb, \ , babbb \}}$

L' élément neutre de la concaténation est la langue, qui ne contient que le mot vide . Ce qui suit s'applique à toutes les langues : ${\ displaystyle L}$

${\ displaystyle L \ circ \ {\ varepsilon \} = \ {\ varepsilon \} \ circ L = L}$

L' élément absorbant de la concaténation est un langage vide, de sorte que pour chaque langue : ${\ displaystyle L \ subseteq \ Sigma ^ {*}}$

${\ displaystyle L \ circ \ {\} = \ {\} \ circ L = \ {\}}$

La concaténation des langues, comme la concaténation des mots, est associative , mais non commutative . Par example:

${\ displaystyle (\ {a, \, bab \} \ circ \ {a, \, b \}) \ circ \ {ab \} = \ {a, \, bab \} \ circ (\ {a, \ , b \} \ circ \ {ab \}) = \ {aaab, \, abab, \, babaab, \, babbab \}}$

mais:

${\ displaystyle \ {a, \, bab \} \ circ \ {a, \, b \} = \ {aa, \, ab, \, baba, \, babb \} \ not = \ {aa, \, abab, \, ba, \, bbab \} = \ {a, \, b \} \ circ \ {a, \, bab \}}$

De plus, puisque l' ensemble de puissance de l'enveloppe de Kleen de tout alphabet (qui est égal à l'ensemble de toutes les langues qui peuvent être formées à partir de ) est fermé par rapport à la concaténation, il forme un monoïde avec la concaténation en tant qu'opérateur et langue du mot vide comme élément neutre . ${\ displaystyle \ Sigma}$${\ displaystyle \ Sigma}$

Puissance

La puissance d' un langage est la double concaténation de ce langage avec lui-même. Il est défini récursivement avec: ${\ displaystyle L ^ {n}}$${\ displaystyle n}$

${\ displaystyle L ^ {0}: = \ {\ varepsilon \}}$

${\ displaystyle L ^ {n + 1}: = L ^ {n} \ circ L}$   (pour )${\ displaystyle n \ in \ mathbb {N} _ {0}}$

Par example:

${\ displaystyle \ lbrace aa, \, abab, \, bbab, \, ba \ rbrace ^ {0} = \ lbrace \ varepsilon \ rbrace}$

${\ displaystyle \ lbrace a, \, b \ rbrace ^ {2} = \ lbrace a, \, b \ rbrace ^ {1} \, \ circ \, \ lbrace a, \, b \ rbrace = (\ lbrace a , \, b \ rbrace ^ {0} \, \ circ \, \ lbrace a, \, b \ rbrace) \, \ circ \, \ lbrace a, \, b \ rbrace = (\ lbrace \ varepsilon \ rbrace \ , \ circ \, \ lbrace a, \, b \ rbrace) \, \ circ \, \ lbrace a, \, b \ rbrace = \ lbrace aa, \, ab, \, ba, \, bb \ rbrace}$

${\ displaystyle \ lbrace a \ rbrace ^ {4} = \ lbrace a \ rbrace \, \ circ \, \ lbrace a \ rbrace \, \ circ \, \ lbrace a \ rbrace \, \ circ \, \ lbrace a \ rbrace = \ lbrace aaaa \ rbrace}$

En particulier, ce qui suit s'applique à chaque élément unique, langage formel (avec ) et à chacun : ${\ displaystyle L = \ lbrace w \ rbrace}$${\ displaystyle w \ in \ Sigma ^ {\ ast}}$${\ displaystyle n \ in \ mathbb {N} _ {0}}$

${\ displaystyle L ^ {n} = \ lbrace w \ rbrace ^ {n} = \ lbrace w ^ {n} \ rbrace}$

Kleene - * - degré et Kleene - + - degré

La fermeture Kleene - * - (enveloppe Kleene, aussi appelée itération ) et la fermeture Kleene - + - (enveloppe positive) d'un langage formel sont définies par l' union des langages puissants de : ${\ displaystyle L ^ {*}}$ ${\ displaystyle L ^ {+}}$${\ displaystyle L}$${\ displaystyle L}$

${\ displaystyle L ^ {*}: = \ bigcup _ {i \ in \ mathbb {N} _ {0}} L ^ {i}}$

 

${\ displaystyle L ^ {+}: = \ bigcup _ {i \ in \ mathbb {N}} L ^ {i}}$

Cours de langue formels importants

1. En 1956, Noam Chomsky a établi une hiérarchie de grammaires formelles qui produisent différents types de langages formels. Ceci est connu aujourd'hui sous le nom de hiérarchie Chomsky . Une distinction est faite entre le type 0, le type 1, le type 2 et le type 3: langages récursivement énumérables , contextuels , sans contexte et réguliers .
2. Aristid Lindenmayer a proposé un système de contrôle dans lequel les étapes de remplacement sont effectuées en parallèle à chaque étape à chaque point. Ces systèmes sont appelés systèmes Lindenmayer .
3. Avec les systèmes semi-Thue , les langues peuvent être définies, qui sont dérivées des mots de départ.
4. Avec les systèmes Church-Rosser, les langues expliquent que leurs mots soient réduits à un mot terminal.
5. Les systèmes de réécriture de termes génèrent l'ensemble des termes qui sont équivalents à un terme de départ.
6. Nous obtenons des généralisations de langages formels avec des grammaires de graphes avec lesquelles nous pouvons générer des langages de graphes.
7. Les grammaires hypergraphiques produisent des hypergraphes , une généralisation des graphes.

Historique

L' écriture conceptuelle de Gottlob Frege est considérée comme l' un des premiers langages formels , comme Frege l'a écrit «le langage des formules de la pensée pure». Le système Semi-Thue d' Axel Thue , qui a été introduit en 1914 et peut être utilisé pour transformer des chaînes, a également influencé le développement des grammaires formelles.

Citation

La recherche fondamentale d'aujourd'hui est maîtrisée

Heinrich Scholz a rencontré Konrad Zuse en 1944 , qui travaillait sur son calcul de plan dans le cadre de sa thèse de doctorat . En mars 1945, Scholz a exprimé son appréciation pour l'application de son calcul logique.

Voir également

• langage construit
• Langage informatique
• Catégorie: Langue formelle - Liste des langues formelles

Applications voir dans:

• Théorie de la calculabilité
• Théorie de la complexité
• Cryptographie
• Cryptanalyse
• Construction du compilateur

Littérature

• Lars Peter Georgie: prévisibilité, complexité, logique . Vieweg, Braunschweig / Wiesbaden,
  • Une troisième édition est parue en 1995.
  • Édition anglaise: Computability, Complexity, Logic . Publié dans la série: Etudes de logique et fondements des mathématiques . Hollande du Nord, Amsterdam 1985.

Une présentation des langages formels dans le contexte de la théorie de la calculabilité, de la logique et de la théorie de la complexité. Exige des exigences élevées pour le lecteur, mais fournit des informations approfondies.

• Michael A. Harrison: Introduction à la théorie formelle du langage . Publié dans la série: Series in Computer Science. Addison-Wesley, 1978.

Une introduction très détaillée et très appréciée.

• John E. Hopcroft et Jeffrey D. Ullman : Introduction à la théorie des automates, aux langages formels et à la théorie de la complexité . Addison-Wesley, 1988.
  • Original anglais: Introduction à la théorie des automates, aux langages et au calcul . Addison-Wesley, 1979.
  • Une troisième édition révisée en allemand a été publiée en 1994 par Oldenbourg R. Verlag GmbH. En 2004, Addison-Wesley a publié une deuxième édition révisée.

L'original anglais est le livre le plus cité en informatique théorique. Les preuves sont parfois déformées dans les anciennes traductions allemandes. Ce livre a été traduit dans de nombreuses langues.

• Grzegorz Rozenberg et Arto Salomaa: La théorie mathématique des L-Systems . Academic Press, New York 1980.

Le livre le plus détaillé sur les systèmes L.

• Grzegorz Rozenberg et Arto Salomaa (éditeurs): Handbook of Formal Languages . Volume I-III, Springer, 1997, ISBN 3-540-61486-9 .

Un aperçu détaillé des domaines les plus importants des langues formelles est présenté par des universitaires actifs dans ce domaine.

• Arto Salomaa: Langues formelles . Springer, 1978.
  • Original anglais: Langues formelles . Presse académique, 1973.
• Ingo Wegener: Informatique théorique . Teubner, Stuttgart 1993, ISBN 3-519-02123-4 .

Dans la représentation des langages formels, la complexité des constructions du langage formel est toujours prise en compte. Sinon, cela ne peut être trouvé que dans la littérature originale.

• U. Hedtstück: Introduction à l'informatique théorique - Langages formels et théorie des automates . Oldenbourg Verlag, Munich 2000, ISBN 3-486-25515-0 .
• S. Abramsky, Dov M. Gabbay, TSE Maibaum (éd.): Manuel de logique en informatique. Vol.5: Méthodes logiques et algébriques. Oxford University Press 2000, ISBN 0-19-853781-6 .
• Mogens Nielsen, Wolfgang Thomas: Logique de l'informatique. Springer 1998, ISBN 3-540-64570-5

Preuve individuelle

1. ↑ Chomsky, Noam (1956). "Trois modèles pour la description de la langue". Transactions IRE sur la théorie de l'information (2): 113-124.
2. ↑ Martin Davis (1995). Influences de la logique mathématique sur l'informatique. Dans Rolf Herken. La machine universelle de Turing: une enquête d'un demi-siècle. Sauteur. P. 290. ISBN 978-3-211-82637-9 .
3. ^ Ronald V. Livre, Friedrich Otto: Systèmes de réécriture de cordes. Springer, 1993, ISBN 0-387-97965-4 , p. 36.
4. ↑ In: Research and Progress n ° 35/36, année 1941, p. 382 et suiv.
5. ↑ Hartmut Petzold : Artistes arithmétiques modernes. L'industrialisation de la technologie informatique en Allemagne. CH Beck Verlag, Munich 1992.