Regular Languages
Summarized notes from Introduction to Theory of Computation, Chapter 1
- recognized equivalently by: DFA, NFA, regular expressions
- closed under union, concatenation, star operation:
- union: \(A \cup B = \{ x | x \in A \text{ or } x \in B \}\)
- concatenation: \(A \circ B = \{ xy | x \in A \text{ and } y \in B \}\)
- star: \(A^* = \{ x_1x_2...x_k | k \geq 0 \text{ and each } x_i \in A \}\)
- satisfy pumping lemma → otherwise nonregular
- finite automaton is the simplest computational model => limited memory but can recognize patterns in data
Deterministic finite automaton (DFA)
5-tuple \((Q, \Sigma, \delta, q_0, F)\)
| \(Q\) | states (finite set) |
| \(\Sigma\) | alphabet (finite set) |
| \(\delta: Q \times \Sigma \rightarrow Q\) | transition function |
| \(q_0 \in Q\) | start state |
| \(F \subseteq Q\) | set of accept (or final) states |
Nondeterministic finite automaton (NFA)
5-tuple \((Q, \Sigma, \delta, q_0, F)\)
| \(Q\) | states (finite set) |
| \(\Sigma\) | alphabet (finite set) |
| \(\delta: Q \times \Sigma_{\epsilon} \rightarrow P(Q)\) | transition function |
| \(q_0 \in Q\) | start state |
| \(F \subseteq Q\) | set of accept (or final) states |
where \(\Sigma_\epsilon\) is \(\Sigma \cup \{ \epsilon \}\) and \(P(Q)\) is the power set of \(Q\).
Regular expression
\(R\) is a regular expression if \(R\) is:
| # | |
|---|---|
| 1. | \(a\) for some \(a\) in alphabet \(\Sigma\), |
| 2. | \(\epsilon\) (empty string), |
| 3. | \(\emptyset\) (empty set), |
| 4. | \((R_1 \cup R_2)\), where \(R_1\) and \(R_2\) are regular expressions, |
| 5. | \((R_1 \circ R_2)\), where \(R_1\) and \(R_2\) are regular expressions, or |
| 6. | \((R^*_1)\) where \(R_1\) is a regular expression |
Generalized nondeterministic finite automaton (GNFA)
- reads blocks symbols from input
- may have any regular expressions as transition labels (or \(\epsilon\), members of \(\Sigma\))
- start state: transition arrows to every other state, no incoming arrows
- single accept state: has incoming arrows from every other state, no outgoing arrows
- all other states (except start and accept): one arrow to every other state and to itself
5-tuple \((Q, \Sigma, \delta, q_{start}, q_{accept})\):
| \(Q\) | states (finite set) |
| \(\Sigma\) | input alphabet |
| \(\delta: (Q - \{ q_{accept}\} \times Q - \{ q_{start}\}) \rightarrow R\) | transition function |
| \(q_{start}\) | start state |
| \(q_{accept}\) | accept state |
Pumping lemma
If \(A\) is a regular language, then there is a number \(p\) (the pumping length) where if \(s\) is any string in \(A\) of length at least \(p\), then \(s\) may be divided into three pieces, \(s = xyz\), satisfying the following conditions:
- for each \(i ≥ 0, xy^{i}z ∈ A\),
- \(|y| > 0\), and
- \(|xy| ≤ p\).