regular languages
(60 minutes to learn)
Summary
A regular language is a formal language which can be defined using a regular expression. Equivalently, it is a language definable as the set of strings accepted by some finite automaton, either deterministic or nondeterministic.
Context
This concept has the prerequisites:
Goals
- Show that regular expressions and finite automata define the same sets of languages
- Be able to show that languages are not regular (e.g. using the Pumping Lemma)
- Prove the Pumping Lemma
Core resources (read/watch one of the following)
-Free-
→ Coursera: Automata
An introductory course on automata and the theory of computation.
-Paid-
→ Introduction to the Theory of Computation
An undergraduate textbook on automata and the theory of computation.
- Section 1.3, "Regular expressions," subsection "Equivalence with finite automata," pages 66-76
- Section 1.4, "Nonregular languages," pages 77-82
→ Automata Theory, Languages, and Computation
An undergraduate textbook on automata and the theory of computation.
- Section 3.2, "Finite automata and regular expressions," pages 92-109
- Section 4.1, "Proving languages not to be regular," pages 128-133
Additional dependencies:
See also
-No Additional Notes-