โ† Theory of Computation learning path
Theory of Computation ยท Module 5 of 10

Properties of regular languages

Pumping lemma, closure and minimisation.

๐Ÿ“– Key ideas

  1. Regular languages are closed under union, concatenation, star, complement and intersection.
  2. The pumping lemma proves a language is not regular: long strings must contain a part that can be repeated.
  3. Classic non-regular languages: {a^n b^n}, balanced parentheses, palindromes.
  4. Myhill-Nerode gives the minimal DFA; table filling merges equivalent states.
  5. 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