Le classique : Introduction to the theory of computation, de Michael Sipser.
Il aborde tous les sujets que t'as mentionné : automates, grammaires algébriques, machines de turing, puis la théorie de la complexité (P=NP, etc).
Pour aller plus en détails :
- Automata and Computability de Dexter Kozen, il fait automates, grammaires et calculabilité, plus en détails, mais il n'aborde pas la complexité (P, NP, etc)
- Complexité algorithmique, de Sylvain Perifel (en français). Il parle uniquement de complexité, très complet. Il faut sans doute commencer par une autre source avant de commencer celui-là.
