We are creating the world's most trusted encyclopedia and knowledge base.
Once you join us and log in, you'll be able to edit this page instantly!

Regular Language

From Citizendium, the Citizens' Compendium

Jump to: navigation, search

Main Article

Talk

Equivalent Characterizations

$A$ is a regular language.
$A$ is accepted by a deterministic finite automaton(DFA).
$A$ is accepted by an alternating finite automaton(AFA).
$A$ is accepted by a non-deterministic finite automaton(NFA).
$A$ is accepted by a generalized non-deterministic finite automaton(GNFA).
$A$ can be described by a regular expression(RE).

Closure Properties

Suppose $A, B \subseteq \Sigma^*$ are regular languages. Then the following languages are also regular.

$A \cup B = \{x ~|~ x \in A\ \mathrm{or}\ x \in B\}$ (union)
$A \cap B = \{x ~|~ x \in A\ \mathrm{and}\ x \in B\}$ (intersection)
$\bar{A} = \{x \in \Sigma^* ~|~ x \not\in A\}$ (complement)
$AB = \{xy ~|~ x \in A\ \mathrm{and}\ y \in B\}$ (concatenation)
$A^* = \{x_1 x_2 \ldots x_n ~|~ n \geq 0\ \mathrm{and}\ x_i \in A,~1 \leq i \leq n\}$ (asterate)
$A - B = \{x - y ~|~ x \in A\ \mathrm{and}\ y \in B\}$ (difference)
$A^R = \{x^R|~ x \in A\ \}$ (reversal)

Regular languages are also closed under homomorphic images and preimages. Suppose $C \subseteq \Gamma^*$ is a regular language and $h : \Sigma^* \to \Gamma^*$ is a string homomorphism. Then the following languages are regular.