# 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-