Regular Language

From Citizendium, the Citizens' Compendium

(Redirected from String (computer science))

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 (computer language))
$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.