On y introduit les notions générales de mot et de langage. On présente ensuite le formalisme des expressions régulières, permettant de décrire une classe importante de langages: les langages rationnels. Les automates à état finis sont ensuite introduits, ainsi que les quelques algorithmes afférents (déterminisation, minimisation...). On montre également comment ces machines permettent de reconnaître les langages rationnels. On présente ensuite la notion de grammaire formelle, et son utilisation pour décrire des langages. Deux sous-classes de grammaires sont étudiées: les grammaires régulières, dont on constatera l'équivalence avec les expressions régulières; puis les grammaires
hors-contexte. Ceci entre dans le cadre de l'étude de la hiérarchie de Chomsky. On donnera une brève introduction à l'analyse de grammaires hors contexte. Finalement, la notion de (semi-)décidabilité d'un langage est introduite et illustrée.