Shared flowchart

Software · L5 · Chomsky Hierarchy

Sign in to clone

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

by @openstemUpdated Software
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

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