You are viewing a free preview of this lesson.
Subscribe to unlock all 10 lessons in this course and every other course on LearningBro.
Regular languages (handled by FSMs and regex) are limited — they cannot describe nested or recursive structures like balanced parentheses or the syntax of programming languages. Context-free languages (CFLs) are a more powerful class that can handle these patterns. They are defined by context-free grammars (CFGs), often written in Backus-Naur Form (BNF).
Languages are classified by their complexity in the Chomsky hierarchy:
| Level | Language Type | Recognised By | Example |
|---|---|---|---|
| 3 | Regular | Finite State Machine | ab |
| 2 | Context-Free | Pushdown Automaton | aⁿbⁿ |
| 1 | Context-Sensitive | Linear-Bounded Automaton | aⁿbⁿcⁿ |
| 0 | Recursively Enumerable | Turing Machine | Any computable language |
Each level is strictly more powerful than the one below it. Regular ⊂ Context-Free ⊂ Context-Sensitive ⊂ Recursively Enumerable.
A context-free grammar consists of:
Subscribe to continue reading
Get full access to this lesson and all 10 lessons in this course.