Salut à tous,

Je ne sais pas si je suis sur le bon compartiment du forum car mon sujet traite de la complexité des mots de Dyck : Auquel cas merci de me le dire

Voila le sujet

Données :
Les mots de Dyck permette le bon "parenthesage" par exemple : ()() OK mais pas ())...
un mot w de longueur n (n>=0) sur l'alphabet {O, F} - "O" représente "(" (ouvrante) et "F" représente ")" (fermante).

Les tâches à réaliser :
1)Une machine de Turing à une bande simple, qui peut être de complexité élevé, et qui reconnaît les mots de Dyck.
2)Une machine de Turing à une bande efficace pour le même problème.

Pour le 1) j'ai trouver un automate de complexité n^2 dans le pire des cas et donc son implémentation sur une machine de Turing à une bande. La contrainte c'est que comme nous sommes sur une machine de Turin g à une bande il nous faut automatiquement un automate déterministe(pour pouvoir l’implémenter XD) et sans pile.

Pour le 2) il faut donc que je diminue la complexité donc soit n*log2(n) soit linéaire mais çà j'y croit pas XD. En tout cas c'est la grande panne sèche tout mes essaye son soit faut reconnaisse mal le langage soit en n^2

Merci d'avance de votre aide