Venn Diagram of Languages with Examples

posted in Theoretical Computer Science on April 23, 2020 by TheBeard

Here is a Venn diagram showing the relative positions of different types of languages.

Here are some example languages for each type

Type	Example
Finite	$\{0\}$
Regular but not Finite	$0^*$
Deterministic Context Free but not Regular	$0^n1^n$
Context Free but not Deterministic Context Free	$\overline{0^n1^n2^n}$
Decidable but not Context Free	$0^n1^n2^n$
Recognizable but not Decidable	$A_{TM}$
Not Recognizable	$\overline{A_{TM}}$

The Beard Sage