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^{\ast }=\{x_1{x}_2...x_k|k\ge 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,\mathrm{\Sigma },\delta ,q_0,F)$

$Q$	states (finite set)
$\mathrm{\Sigma }$	alphabet (finite set)
$\delta :Q\times \mathrm{\Sigma }\to 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,\mathrm{\Sigma },\delta ,q_0,F)$

$Q$	states (finite set)
$\mathrm{\Sigma }$	alphabet (finite set)
$\delta :Q\times {\mathrm{\Sigma }}_{ϵ}\to P(Q)$	transition function
$q_0\in Q$	start state
$F\subseteq Q$	set of accept (or final) states

where ${\mathrm{\Sigma }}_{ϵ}$ is $\mathrm{\Sigma }\cup \{ϵ\}$ 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 $\mathrm{\Sigma }$,
2.	$ϵ$ (empty string),
3.	$\mathrm{\varnothing }$ (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^{\ast })$ 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 $ϵ$, members of $\mathrm{\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,\mathrm{\Sigma },\delta ,q_{start},q_{accept})$:

$Q$	states (finite set)
$\mathrm{\Sigma }$	input alphabet
$\delta :(Q-\{q_{accept}\}\times Q-\{q_{start}\})\to 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:

1. for each $i\ge 0,x{y}^{i}z\in A$,
2. $|y|>0$, and
3. $|xy|\le p$.