Featured Programs
Experiential Learning Opportunities
Claim up to $1,000 in flight credits!
Get up to $1,000 in flight credits or grants toward study or internship programs abroad when you apply by January 01, 2025. See our Official Rules for full details.
Automata Theory and Compilers
Engineering & Social Sciences Program
Madrid, Spain
Dates: 8/30/21 - 12/23/21
Automata Theory and Compilers
OVERVIEW
CEA CAPA Partner Institution: Universidad Carlos III de Madrid
Location: Madrid, Spain
Primary Subject Area: Computer Sciences
Instruction in: English
Course Code: 16491
Transcript Source: Partner Institution
Course Details: Level 200
Recommended Semester Credits: 3
Contact Hours: 42
Prerequisites: Programming, Algorithms and Data Structures
DESCRIPTION
1.Introduction to the theory of automata and formal languages.
1.1. Why study Automata Theory. History and Origins
1.2. Relationship with others Areas of Knowledge
1.3. Machines, Languages and Algorithms.
2.- Automata Theory
2.1 Introduction and Definitions.
2.2 Mathematical model of an automaton
2.3 Automata and algorithms.
2.4 Discrete, continuous, and hybrid automata. Classes of automata.
3.Finite Automata
3.1 Definition and Representation of Deterministic Finite Automata (DFA)
3.2. DFA as Recognition Device
3.3. Equivalence and Minimization of DFA
3.4. Theorems of DFA
3.5. Definition and Representation of Nondeterministic Finite Automata (NDFA)
3.6. The Language of a NDFA
3.7. Equivalence of DFA and NDFA
4.Languages and Formal Grammars.
4.1. Operations with Words. Operations with Languages. Derivations.
4.2 Concept of Grammar. Formal Grammar.
4.3. Chomsky Hierarchy and Equivalent Grammar
4.4 Context-Free Grammar
4.5. Language of a Context-Free Grammar. Parse Tree
4.6. Well-Formed Grammar
4.7. Chomsky Normal Form. Greibach Normal Form
5.Regular Languages.
5.1. Definition of Regular Languages
5.2. DFA for a Regular Grammar
5.3. Equivalence of Regular Expressions
5.4. Kleene's Theorem
5.5. Characteristic equations
5.6. Synthesis Problem: Recursive Algorithm
5.7. Derivatives of Regular Expressions
6.Pushdown Automata.
6.1. Definition of Pushdown Automata (PDA).
6.2. Transitions, Movement and Instantaneous Description in PDA.
6.3. Acceptance by Empty Stack. Acceptance by Final State.
6.4. Language Accepted by a PDA.
Equivalence of PDA by Empty Stack and PDA by Final State.
6.5. From Context-Free Grammar to Push-Down Automata.
6.6. From Pushdown Automata to Context-Free Grammar.
7.Turing Machine.
7.1. Definition if Turing Machine.
7.2. Variations of Turing Machine.
7.3. Universal Turing Machine.
8.Computational Complexity
8.1.Complexity Theory
8.2.Complexity of algorithms
8.3.P versus NP problems
8.4 Defining complexity classes
8.5 Time complexity
8.6 Hierarchy theorems
8.7 Non-computational problems
8.9 Limits of Computability
1.1. Why study Automata Theory. History and Origins
1.2. Relationship with others Areas of Knowledge
1.3. Machines, Languages and Algorithms.
2.- Automata Theory
2.1 Introduction and Definitions.
2.2 Mathematical model of an automaton
2.3 Automata and algorithms.
2.4 Discrete, continuous, and hybrid automata. Classes of automata.
3.Finite Automata
3.1 Definition and Representation of Deterministic Finite Automata (DFA)
3.2. DFA as Recognition Device
3.3. Equivalence and Minimization of DFA
3.4. Theorems of DFA
3.5. Definition and Representation of Nondeterministic Finite Automata (NDFA)
3.6. The Language of a NDFA
3.7. Equivalence of DFA and NDFA
4.Languages and Formal Grammars.
4.1. Operations with Words. Operations with Languages. Derivations.
4.2 Concept of Grammar. Formal Grammar.
4.3. Chomsky Hierarchy and Equivalent Grammar
4.4 Context-Free Grammar
4.5. Language of a Context-Free Grammar. Parse Tree
4.6. Well-Formed Grammar
4.7. Chomsky Normal Form. Greibach Normal Form
5.Regular Languages.
5.1. Definition of Regular Languages
5.2. DFA for a Regular Grammar
5.3. Equivalence of Regular Expressions
5.4. Kleene's Theorem
5.5. Characteristic equations
5.6. Synthesis Problem: Recursive Algorithm
5.7. Derivatives of Regular Expressions
6.Pushdown Automata.
6.1. Definition of Pushdown Automata (PDA).
6.2. Transitions, Movement and Instantaneous Description in PDA.
6.3. Acceptance by Empty Stack. Acceptance by Final State.
6.4. Language Accepted by a PDA.
Equivalence of PDA by Empty Stack and PDA by Final State.
6.5. From Context-Free Grammar to Push-Down Automata.
6.6. From Pushdown Automata to Context-Free Grammar.
7.Turing Machine.
7.1. Definition if Turing Machine.
7.2. Variations of Turing Machine.
7.3. Universal Turing Machine.
8.Computational Complexity
8.1.Complexity Theory
8.2.Complexity of algorithms
8.3.P versus NP problems
8.4 Defining complexity classes
8.5 Time complexity
8.6 Hierarchy theorems
8.7 Non-computational problems
8.9 Limits of Computability