Venn Diagram of Languages with Examples

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

Here are some example languages for each type

Regular but not Finite0^*
Deterministic Context Free but not Regular0^n1^n
Context Free but not Deterministic Context Free\overline{0^n1^n2^n}
Decidable but not Context Free0^n1^n2^n
Recognizable but not DecidableA_{TM}
Not Recognizable\overline{A_{TM}}

Leave a Reply

Your email address will not be published. Required fields are marked *