Email Address:

Phone Number:

Automata and Complexity- Period 4 Social Sciences & Humanities Program Spring 2025 Semester - Amsterdam

Flight Credit Get a Flight Credit worth up to $1,000 when you apply with code* by September 12, 2024

Automata and Complexity- Period 4

Automata and Complexity- Period 4 Course Overview


CEA CAPA Partner Institution: Vrije Universiteit Amsterdam
Location: Amsterdam, Netherlands
Primary Subject Area: Computer Sciences
Instruction in: English
Course Code: X_401049
Transcript Source: Partner Institution
Course Details: Level 300
Recommended Semester Credits: 3
Contact Hours: 84


The first part, on automata and languages, deals with the concepts of formal language, grammar, and automaton. Two types of languages are covered: regular and context-free languages. Regular languages are used, e.g., in search queries, in the form of regular expressions. Context-free languages are suitable to describe programming languages. The automata-theoretic counterparts here are finite automata and the more powerful pushdown automata. Pumping lemmas are discussed to determine whether a language is regular or context-free. With each type of language a class of grammars is associated: left-linear and context-free grammars. Parsing algorithms are presented for context-free languages, to determine whether a string is in the language.

In the second part of the course, on computability theory, the central question is "Which computations can be performed on a computer?". To reason about this question, Turing machines are introduced, as well the Church-Turing thesis, along with examples of undecidable problems: the halting problem and the Post correspondence problem. It is shown how undecidability of new problems can be shown by reduction from a known undecidable problem. Important complexity classes from the complexity hierarchy are discussed, notably P, NP, and NP-complete, together with the corresponding reduction arguments.

Contact hours listed under a course description may vary due to the combination of lecture-based and independent work required for each course therefore, CEA's recommended credits are based on the ECTS credits assigned by VU Amsterdam. 1 ECTS equals 28 contact hours assigned by VU Amsterdam.

Receive a $1,000 Flight Credit when you apply by September 12, 2024

Get your flight credit code and access to Passbook in two easy steps. With Passbook, you can track your favorite programs and courses, save flight credits, and watch videos on the destination you're interested in.

Apply Now

Step 1 of 2

Step 2 of 2

*By providing your mobile number, you agree to receive recurring text messages from CEA CAPA Education Abroad notifying you of important program deadlines. Message and data rates may apply.

Privacy Policy   |   Mobile Terms   |   Flight Credit Rules

Your flight credit has been added to your Passbook. Apply now or view your Passbook to begin the next step in your journey.