โ Theory of Computation learning pathTheory of Computation ยท Module 5 of 10
Properties of regular languages
Pumping lemma, closure and minimisation.
๐ Key ideas
- Regular languages are closed under union, concatenation, star, complement and intersection.
- The pumping lemma proves a language is not regular: long strings must contain a part that can be repeated.
- Classic non-regular languages: {a^n b^n}, balanced parentheses, palindromes.
- Myhill-Nerode gives the minimal DFA; table filling merges equivalent states.
- Decision problems for regular languages (emptiness, equality) are decidable.
๐ก Real-life example: The pumping lemma is like noticing that a long walk in a small park must pass the same bench twice, so you could loop there as many times as you like.
Pumping lemmaTool to prove a language is not regular
Closure propertyOperation that keeps results in the class
Minimal DFADFA with the fewest states for a language
Myhill-Nerode theoremCharacterises regular languages by equivalence classes