Qu'est-ce qu'une langue ordinaire ?

Question

J'essaie de comprendre le concept des niveaux de langues (régulier, sans contexte, sensible au contexte, etc.).

Je peux faire des recherches facilement, mais toutes les explications que je trouve sont un tas de symboles et parlent de fixe . J'ai deux questions :

1. Pouvez-vous décrire en quelques mots ce qu'est une langue ordinaire, et en quoi les langues diffèrent ?

2. Où les gens apprennent-ils à comprendre ce genre de choses ? Si je comprends bien, il s'agit de mathématiques formelles ? J'ai suivi quelques cours à l'université qui l'utilisaient et presque personne ne l'a compris car les tuteurs supposaient simplement que nous le savions. Où puis-je l'apprendre et pourquoi les gens sont-ils "censés" le connaître dans tant de sources ? C'est comme s'il y avait une lacune dans l'éducation.

Voici un exemple :

Tout langage appartenant à cet ensemble est un langage régulier sur l'alphabet.

Comment une langue peut-elle être "au-dessus" de quelque chose ?

Answer 1

Dans le contexte de l'informatique, un mot est la concaténation de symboles . Les symboles utilisés sont appelés alphabet . Par exemple, certains mots formés à partir de l'alphabet {0,1,2,3,4,5,6,7,8,9} serait 1 , 2 , 12 , 543 , 1000 y 002 .

A langue est alors un sous-ensemble de tous les mots possibles. Par exemple, on peut vouloir définir un langage qui englobe tous les agents d'élite du MI6. Ceux-ci commencent tous par un double-0, donc les mots du langage seraient les suivants 007 , 001 , 005 y 0012 mais pas 07 o 15 . Pour simplifier, nous dirons qu'une langue est " sur un alphabet" au lieu de "un sous-ensemble de mots formé par la concaténation de symboles sur un alphabet".

En informatique, nous voulons maintenant classer les langages. Nous appelons un langage régulier si l'on peut décider si un mot est dans la langue à l'aide d'un algorithme/d'une machine à mémoire constante (finie) en examinant tous les symboles du mot l'un après l'autre. Le langage constitué uniquement du mot 42 est régulier, car vous pouvez décider si un mot s'y trouve sans avoir besoin d'une quantité arbitraire de mémoire ; vous vérifiez simplement si le premier symbole est 4, si le second est 2, et si d'autres chiffres suivent.

Tous les langages avec un nombre fini de mots sont réguliers, parce que nous pouvons (en théorie) construire un arbre de flux de contrôle de taille constante (vous pouvez le visualiser comme un tas de mots imbriqués). if -des déclarations qui examinent un chiffre après l'autre). Par exemple, nous pouvons tester si un mot est dans le langage "nombres premiers entre 10 et 99" avec la construction suivante, ne nécessitant aucune mémoire sauf celle pour encoder à quelle ligne de code nous nous trouvons actuellement :

if word[0] == 1:
  if word[1] == 1: # 11
      return true # "accept" word, i.e. it's in the language
  if word[1] == 3: # 13
      return true
...
return false

Notez que tous les langages finis sont réguliers, mais que tous les langages réguliers ne sont pas finis ; notre langage double-0 contient un nombre infini de mots ( 007 , 008 mais aussi 004242 y 0012345 ), mais peut être testé à mémoire constante : Pour tester si un mot y appartient, vérifiez si le premier symbole est 0 et si le second symbole est 0 . Si c'est le cas, acceptez-le. Si le mot est plus court que trois ou ne commence pas par 00 ce n'est pas un nom de code du MI6.

Formellement, la construction d'un machine à états finis ou un grammaire régulière est utilisé pour prouver qu'un langage est régulier. Elles sont similaires aux if Les déclarations ci-dessus, mais permettent des mots arbitrairement longs. S'il existe une machine à états finis, il existe aussi une grammaire régulière, et vice versa, il suffit donc de montrer l'une ou l'autre. Par exemple, la machine à états finis pour notre langage double-0 est :

start state:  if input = 0 then goto state 2
start state:  if input = 1 then fail
start state:  if input = 2 then fail
...
state 2: if input = 0 then accept
state 2: if input != 0 then fail
accept: for any input, accept

La grammaire régulière équivalente est :

start  0 B
B  0 accept
accept  0 accept
accept  1 accept
...

L'équivalent expression régulière est :

00[0-9]*

Certaines langues sont pas régulier. Par exemple, la langue d'un nombre quelconque de 1 suivi du même nombre de 2 (souvent écrit comme 1 n 2 n pour une valeur arbitraire de n ) n'est pas régulier - il faut plus qu'une quantité constante de mémoire (= un nombre constant d'états) pour stocker le nombre de 1 pour décider si un mot fait partie de la langue.

Cela devrait généralement être expliqué dans le cours d'informatique théorique. Heureusement, Wikipedia explique les deux officiel y langues régulières assez bien.

Answer 2

Voici quelques-unes des définitions équivalentes tirées de Wikipedia :

[...] un langage régulier est un langage formel (c'est-à-dire un ensemble éventuellement infini de f ensemble éventuellement infini de séquences finies de symboles issus d'un alphabet fini) qui satisfait aux propriétés équivalentes suivantes :

• il peut être accepté par une machine à états finis déterministe.

• il peut être accepté par une machine à états finis non déterministe

• il peut être décrit par une expression régulière formelle.

  Notez que les fonctions d'"expression régulière" fournies avec de nombreux langages de programmation sont complétées par des fonctionnalités qui les rendent capables de reconnaître langages qui ne sont pas réguliers, et ne sont donc pas strictement pas strictement équivalentes aux expressions régulières formelles.

La première chose à noter est qu'un langage régulier est un langage formel avec certaines restrictions. Un langage formel est essentiellement une collection (éventuellement infinie) de chaînes de caractères. Par exemple, le langage formel Java est la collection de tous les fichiers Java possibles, qui est un sous-ensemble de la collection de tous les fichiers texte possibles.

L'une des caractéristiques les plus importantes est que, contrairement aux les langages sans contexte Un langage régulier ne supporte pas l'imbrication/récursion arbitraire, mais vous avez la répétition arbitraire.

Une langue a toujours un alphabet sous-jacent qui est l'ensemble des symboles autorisés. Par exemple, l'alphabet d'un langage de programmation est généralement l'ASCII ou l'Unicode, mais dans la théorie formelle des langues, il est également possible de parler de langues sur d'autres alphabets, par exemple l'alphabet binaire où les seuls caractères autorisés sont les suivants 0 y 1 .

Dans mon université, on nous enseignait un peu de théorie formelle des langages dans le cours sur les compilateurs, mais cela varie probablement d'une école à l'autre.

Answer 3

J'ai appris la plupart de ce genre de choses de la part de "Introduction à la théorie du calcul", par Michael Sipser Je l'ai trouvé très utile.

En voici le contenu :

• Introduction
• Partie 1 : Automates et langages
  • 1. Langues régulières
  • 2. Langages sans contexte
• Partie 2 : Théorie de la calculabilité
  • 3. La thèse de Church-Turing
  • 4. Décidabilité
  • 5. Réductibilité
  • 6. Sujets avancés en théorie de la calculabilité
• Partie 3 : Théorie de la complexité
  • 7. Complexité du temps
  • 8. Complexité de l'espace
  • 9. Intraductibilité
  • 10. Sujets avancés en théorie de la complexité.