Regular Languages & Regex

By the end, you can

• Name the three primitive regex operations and state their precedence.
• Apply precedence rules to parse an ambiguous regex expression correctly.
• Identify which strings a given regex accepts or rejects.
• Explain Kleene's theorem and describe the conversion chain regex → NFA → DFA → regex.
• Explain why an NFA is not more powerful than a DFA.
• List the closure properties of regular languages and explain how complement is constructed.
• Explain why {a^n b^n} is not regular in terms of finite memory.
• State the three constraints of the pumping lemma (|y| ≥ 1, |xy| ≤ p, pumping holds for all i ≥ 0).
• Walk through the pumping-lemma proof by contradiction for {a^n b^n}.
• Explain why the pumping lemma is necessary but not sufficient for regularity.
• Distinguish true regular expressions from practical regex engines (PCRE), and explain what features exceed the regular class.