Semestre 4

This course aims to study the theory of formal languages in computer science, highlighting the importance of formal languages in the automation of computational processes with algorithms, computability theory, automata theory, natural language processing, and bioinformatics. Through this course, we provide fundamental concepts related to formal languages, grammars, automata, and regular expressions. In addition, the manual includes a series of exercises and practical assignments aimed at reinforcing understanding and facilitating the application of these concepts in real-world scenarios. We will begin with foundational building blocks such as alphabets, symbols, words, languages and operations on languages. From there, we will progress to more powerful language models by studying the theory of generative grammars and the language hierarchy in order to understand language analyzers (scanners and parsers). This leads us in to study the recognition automata and this aims to provide a deep understanding of the representation and operational modes of finite automata and pushdown automata, including their behaviors , decidability, complexity, and the related optimization algorithms.