arf il faut éviter de trop voir ça noir/blanc:
Il n’y a pas d’un coté l’info théorique et de l’autre la pratique.
Si on veut faire de l’info « pratique » qui ne consiste pas qu’à coder des algos déjà tous faits (ce qui est un métier technique en soit), il faut avoir un peu de background en info théorique. Par contre, si on est « utilisateur » de l’info (en tant par ex que physicien) alors on ne va pas formaliser les preuves car on s’en fiche.
L’exemple de Marc de Falco résume bien tout cela (le coup du lex…)
Sualty a écrit:
j’avais pensé que tous les mots bien parenthésés de longueur n+2 pouvaient s’obtenir à partie des mots de longueurs n en faisant les concaténations suivantes :
(x)
( )x
x( )
avec x les mots de longueur n
Et bien sûr, pour les premiers cas ça fonctionne,mais après il m’en manque !
C’est bien vu, mais regarde bien ta définition: dans la seconde et 3e règle tu ne pourras pas avoir qq chose du type (())(x) ou bien (x)(()) et bien sûr plein d’autres.
Pour résumer et construire sur ce que tu dis :
bien parenthésé : une ouvrante, puis un truc bien parenthésé, la fermante correspondante, et après encore un autre truc bien parenthésé. Du coup la récurrence devient :
soient x et y deux mots bien parenthésés, alors (x)y l’est.
Petit problème : comment obtenir avec ce processus ()() : on voit qu’il faut étendre la définition (et donc la fin de la récurrence) en intégrant le mot vide.
Je vous laisse poursuivre tout seul, c’est assez rigolo. 
Ca me semble être d’une structure d’automates à piles.
En fait l’algo c’est une bête pile vide.
On empile sur une ouvrante et on dépile sur une fermante.
On doit vérifier qu’à la fin la pile et vide et qu’aucune des opérations de dépilage n’échoue.
On peut très bien faire ca avec un bete entier:
Sur ()() ca donne
0 1 0 1 0 donc c’est bon.
Sur (())) ca dont 0 1 2 1 0 PAF on passerait négatif donc c’est rejeté.
Point besoin de coder une vraie pile.
heu c’est totalement trivial…enfin je croyais…
Une idée : un mot bien parenthésé de taille 2n (n>1) s’obtient de façon unique comme (x)y, où x et y sont des mots bien parenthésés de taille éventuellement nulle, dont la somme des tailles vaut 2(n-1).
edit : argh, j’avais vu que la première page de discussion… ce que je dis est un peu redondant 
c’est aussi assimile a une machine de Turing, ou l’etat acceptant correspond a un ruban vide et l’etat final
cad: on construit deux etats a s’interchanger a chaque lecture de ( ou )