Dans cette thèse, nous étudions des questions algorithmiques relatives aux langages formels, pour lesquels nous donnons des algorithmes d'approximation efficaces (en termes de ressources).
Dans la première partie, nous nous intéressons aux problèmes algorithmiques liés au problème de recherche approximative de motif, c'est-à-dire la tâche qui consiste à trouver toutes les sous-chaînes d'un texte similaires à un motif donné. Nous considérons plusieurs notions de similarité, notamment à rotation, substitutions ou éditions, et notamment dans le cas des chaînes de caractères contenant des jokers.
La seconde partie s'intéresse à la question d'approximer l'appartenance d'un mot à un langage formel, dans trois contextes différents : le property testing des langages réguliers, dont nous caractérisons la complexité avec un résultat de trichotomie, le calcul de la distance entre un mot et un langage formel dans le cas des palindromes et des carrés, ainsi que le calcul de la longueur palindromique d'un mot.