@openstem shared this flowchart

Software · L5 · Chomsky Hierarchy

The strict containment of language classes and their corresponding recognising automata.

Software
Updated
0
0
Read only
Type 0: Recursively Enumerable (Turing machine)Type 1: Context-Sensitive (linear-bounded automaton)Type 2: Context-Free (pushdown automaton)Type 3: Regular (finite automaton)Regular expressions (Kleene 1956)Not regular (pumping lemma)Not context-free (CFG pumping lemma)described bywitness: a^n b^nwitness: a^n b^n c^n
Browse Software

We use privacy-friendly product analytics (no session recording, PII masked) to improve OpenStem. Load analytics? Privacy Policy