regular language

a language is called a regular language if some finite automaton recognizes it.
[cite:@sipser_comp_2012 definition 1.16]

the class of regular languages is closed under the concatenation operation. given regular languages $\text{[math]}$ and $\text{[math]}$ , we can construct a finite automaton that recognizes $\text{[math]}$ .
[cite:@sipser_comp_2012 theorem 1.26]
[cite:@sipser_comp_2012 theorem 1.47]

the class of regular languages is closed under the star operation.
[cite:@sipser_comp_2012 theorem 1.49]

the class of regular languages is closed under union.
[cite:@sipser_comp_2012 theorem 1.25]
[cite:@sipser_comp_2012 theorem 1.45]

we have regular languages $\text{[math]}$ and $\text{[math]}$ and want to prove that $\text{[math]}$ is regular. the idea is to take two NFAs, $\text{[math]}$ and $\text{[math]}$ for $\text{[math]}$ and $\text{[math]}$ , and combine them into one new NFA, $\text{[math]}$ .
machine $\text{[math]}$ must accept its input if either $\text{[math]}$ or $\text{[math]}$ accepts this input. the new machine has a new start state that branches to the start states of the old machines with $\text{[math]}$ arrows. in this way, the new machine nondeterministically guesses which of the two machines accepts the input. if one of them accepts the input, $\text{[math]}$ will accept it, too.
we represent this construction in fig-reglang-1. on the left, we indicate the start and accept states of machines $\text{[math]}$ and $\text{[math]}$ with large circles and some additional states with small circles. on the right, we show how to combine $\text{[math]}$ and $\text{[math]}$ into $\text{[math]}$ by adding additional transition arrows.
$\text{[math]}$ let $\text{[math]}$ recognize $\text{[math]}$ , and $\text{[math]}$ recognize $\text{[math]}$ .
construct $\text{[math]}$ to recognize $\text{[math]}$ .

$\text{[math]}$ . the states of $\text{[math]}$ are all the states of $\text{[math]}$ and $\text{[math]}$ , with the addition of a new start state $\text{[math]}$ .
the state $\text{[math]}$ is the start state of $\text{[math]}$ .
the set of accept states $\text{[math]}$ . the accept states of $\text{[math]}$ are all the accept states of $\text{[math]}$ and $\text{[math]}$ . that way, $\text{[math]}$ accepts if either $\text{[math]}$ accepts or $\text{[math]}$ accepts.
define $\text{[math]}$ so that for any $\text{[math]}$ and any $\text{[math]}$ , \begin{equation} \delta(q,a) = $\text{[math]}$ \end{equation}

[cite:@sipser_comp_2012 theorem 1.45]

if $\text{[math]}$ is a DFA that recognizes language $\text{[math]}$ , swapping the accept and nonaccept states in $\text{[math]}$ yields a new DFA recognizing the complement of $\text{[math]}$ . consequently, the class of regular languages is closed under complement.
[cite:@sipser_comp_2012 exercise 1.14]

the class of regular languages is closed under difference.
[cite:@lewenstein_automata]

the class of regular languages is closed under intersection.

let $\text{[math]}$ recognize $\text{[math]}$ , where $\text{[math]}$ , and $\text{[math]}$ recognize $\text{[math]}$ , where $\text{[math]}$ .
construct $\text{[math]}$ to recognize $\text{[math]}$ , where $\text{[math]}$ .

$\text{[math]}$ . this set is the cartesian product of sets $\text{[math]}$ and $\text{[math]}$ and is written $\text{[math]}$ .
$\text{[math]}$ , the alphabet, is the same as in $\text{[math]}$ and $\text{[math]}$ . we assume for simplicity that both $\text{[math]}$ and $\text{[math]}$ have the same input alphabet $\text{[math]}$ . the theorem remains true if they have different alphabets, $\text{[math]}$ . we would then modify the proof to let $\text{[math]}$ .
$\text{[math]}$ , the transition function, is defined as follows. for each $\text{[math]}$ and each $\text{[math]}$ , let $\text{[math]}$ . hence $\text{[math]}$ gets a state of $\text{[math]}$ (which actually is a pair of states from $\text{[math]}$ and $\text{[math]}$ , together with an input symbol, and returns $\text{[math]}$ next state.
$\text{[math]}$ is the pair $\text{[math]}$ .
$\text{[math]}$

we propose the following equivalence from the definition of $\text{[math]}$ , which will help us:
$\text{[math]}$ where $\text{[math]}$ , and so by induction, we can turn it into:
$\text{[math]}$ we need to show that
$\text{[math]}$ by [[blk:def-dfa-reglang][definition]], the language that $\text{[math]}$ recognizes is
$\text{[math]}$ by eq-reglang-1, [[blk:eq-reglang-2]] and eq-reglang-3 are equivalent.

[cite:@lewenstein_automata]
[cite:@sipser_comp_2012]

let $\text{[math]}$ be regular languages, we denote by $\text{[math]}$ the language of those words in $\text{[math]}$ that have a prefix in $\text{[math]}$ . prove that $\text{[math]}$ is a regular language.

let $\text{[math]}$ be the DFAs of $\text{[math]}$ , respectively. we can construct the DFA that recognizes $\text{[math]}$ as:
$\text{[math]}$ where $\text{[math]}$ and $\text{[math]}$ .
for simplicity its assumed that $\text{[math]}$ are over the same alphabet, so $\text{[math]}$ , the proof that $\text{[math]}$ recognizes $\text{[math]}$ can be done by induction.

let $\text{[math]}$ be a regular language, define $\text{[math]}$ . describe $\text{[math]}$ with words and prove $\text{[math]}$ is a regular language

$\text{[math]}$ is the language of the suffixes of words from $\text{[math]}$ .
let $\text{[math]}$ be a dfa such that $\text{[math]}$ , let $\text{[math]}$ where $\text{[math]}$ where $\text{[math]}$ . here we're treating the transition function as a set (or table) of 3-tuples where the first is the source state, the second is the symbol and the third is the destination state (informal). $\text{[math]}$ recognizes $\text{[math]}$ .

let $\text{[math]}$ , prove $\text{[math]}$ is a regular language.

let $\text{[math]}$ be the DFAs recognizing $\text{[math]}$ , i.e. $\text{[math]}$ , such that $\text{[math]}$ , we define $\text{[math]}$ such that $\text{[math]}$ . the NFA $\text{[math]}$ recognizes $\text{[math]}$ . this works because the words are disjoint (dont share the same letters).

regular languages are closed under reversal.

let $\text{[math]}$ be a regular language, prove $\text{[math]}$ is a regular language.

let $\text{[math]}$ be a DFA such that $\text{[math]}$ , define $\text{[math]}$ such that $\text{[math]}$ . $\text{[math]}$ recognizes $\text{[math]}$ .

the language $\text{[math]}$ is irregular.

assume in contradiction that $\text{[math]}$ is regular, by [[blk:lem-reglang-difference-closure]], regular languages are closed under difference, so the language $\text{[math]}$ would also be regular, but this contradicts with [[blk:exa-pumping-lemma-1]], which means that our assumption that $\text{[math]}$ is regular cannot be true.

let $\text{[math]}$ be a regular language, $\text{[math]}$ , defined by
$\text{[math]}$ is also a regular language.
[cite:@lewenstein_automata]

let $\text{[math]}$ be a DFA such that $\text{[math]}$ , we construct $\text{[math]}$ such that $\text{[math]}$ .
the idea is: for every state in $\text{[math]}$ that has a path to an accept state in $\text{[math]}$ we define an accept state in $\text{[math]}$ , the construction is as follows:
$\text{[math]}$ we need to show the correctness of the construction, i.e. $\text{[math]}$ , we show this by double inclusion, for $\text{[math]}$ : $\text{[math]}$ such that $\text{[math]}$ such that $\text{[math]}$ where $\text{[math]}$ . i.e. there exists $\text{[math]}$ such that $\text{[math]}$ where $\text{[math]}$ . thus $\text{[math]}$ and thus $\text{[math]}$ where $\text{[math]}$ (because the transitions of $\text{[math]}$ are the same as those of $\text{[math]}$ ) and thus $\text{[math]}$ . for $\text{[math]}$ : $\text{[math]}$ where $\text{[math]}$ . because the transitions in $\text{[math]}$ are similar to those in $\text{[math]}$ and $\text{[math]}$ , $\text{[math]}$ where $\text{[math]}$ such that $\text{[math]}$ (by definition of $\text{[math]}$ ). thus there exists $\text{[math]}$ such that $\text{[math]}$ thus $\text{[math]}$ .

given $\text{[math]}$ are regular languages, $\text{[math]}$ , defined by
$\text{[math]}$ is also a regular language.
[cite:@lewenstein_automata]