Réponse:   Le langage des parenthèses L ne peut pas être reconnu par une expression régulière. Sinon, il serait reconnaissable par un automate fini. Or, les ensembles L_n= {w | gⁿ w Î L} des suffixes des mots de L commençants par gⁿ sont deux à deux distincts (au moins un mot est dans l'un mais pas dans l'autre). Il faudrait donc un nombre d'états arbitraires à un automate pour disntinguer l'ensemble des configurations possibles au cours de la reconnaissance d'une expression.

L peut être reconnu par un lexeur mais seulement en utilisant la puissance du langage hôte (qui est un complet en général) dans les actions du lexeur pour compter les parenthèses ouvertes.