This course provides a comprehensive study of formal languages, covering regular languages, context-free languages, and recursively enumerable languages.

What are the mathematics behind computers? What are the theoretical foundations of computer languages? Such questions can be explored by understanding formal languages and automata models. 

In this comprehensive course, you’ll explore formal languages, regular languages, and how to model them with their associated automata models. Next, you’ll cover regular expressions and grammar, and their equivalents. Then, you’ll explore context-free languages (the foundations of programming languages), pushdown automata, and the relationship between them. Toward the end, you’ll learn about recursively enumerable languages, Turing machines with their variations, context-sensitive languages, and unrestricted grammars.

By the end of the course, you’ll have gained a deep understanding of several formal languages and their associated automata. Also, since there are plenty of exercises throughout the course, your understanding and problem-solving skills will be thoroughly reinforced.

Theory of Computation

We can now summarize the entire hierarchy of formal languages. We emphasize "hierarchy" because each language class is a subset of the class above it. This classification originated with Noam Chomsky and is aptly called the **Chomsky hierarchy**. See the following table.

|**Language Class**|**Recognizing Machine**|**Grammar Type**|
|-------|-------|--------|
|Recursively Enumerable| $\text{TM}$ (recognizer) | Type 0: Unrestricted |
|Recursive| $\text{TM}$ (decider) |Type 0: Unrestricted|
|Context Sensitive| LBA (bounded $\text{TM}$) | Type 1: Non-contracting |
|Context Free|PDA| Type 2: Context Free|
|Deterministic Context Free|DPDA|Type 2: Context Free|
|Regular| DFA|Type 3: Right/Left Linear

Learn about the Chomsky hierarchy of formal languages and the existence of languages that are not recursively enumerable.


Getting Started

Exam on Formal Languages

Finite Automata

Exam on Finite Automata

Regular Expressions and Grammars

Exam on Regular Expressions and Grammars

Properties of Regular Languages

Exam on Properties of Regular Languages

Pushdown Automata

Exam on Pushdown Automata

Context-Free Grammars

Exam on Context-Free Grammars

Properties of Context-Free Languages

Exam on Properties of Context-Free Languages

Turing Machines

Exam on Turing Machines

The Landscape of Formal Languages

Exam on the Landscape of Formal Languages

Computability

Exam on Computability

Conclusion

The Chomsky Hierarchy

Language Class	Recognizing Machine	Grammar Type
Recursively Enumerable	$\text{TM}$ (recognizer)	Type 0: Unrestricted
Recursive	$\text{TM}$ (decider)	Type 0: Unrestricted
Context Sensitive	LBA (bounded $\text{TM}$ )	Type 1: Non-contracting
Context Free	PDA	Type 2: Context Free
Deterministic Context Free	DPDA	Type 2: Context Free
Regular	DFA	Type 3: Right/Left Linear