You are viewing a free preview of this lesson.
Subscribe to unlock all 10 lessons in this course and every other course on LearningBro.
Formal languages are classified into a hierarchy based on their complexity and the type of automaton required to recognise them. This classification, known as the Chomsky hierarchy, is a fundamental part of OCR H446 section 1.4.
A formal language is a set of strings formed from a given alphabet (set of symbols) according to specific rules (grammar).
| Concept | Definition | Example |
|---|---|---|
| Alphabet | A finite set of symbols | {0, 1} or {a, b, c, ..., z} |
| String | A finite sequence of symbols from the alphabet | "0110", "hello" |
| Language | A set of strings (possibly infinite) | All binary strings of even length |
| Grammar | A set of rules for generating valid strings | BNF production rules |
Noam Chomsky classified formal languages into four types, from most restricted to most general:
Subscribe to continue reading
Get full access to this lesson and all 10 lessons in this course.