Regular Expression

[!math|{“type”:“definition”,“number”:“auto”,“setAsNoteMathLink”:false,“title”:“Regular Expression”,“label”:“regular-expression”,“_index”:0}] Definition 1 (Regular Expression). $R$ is a regex if $R$ is

• $a\in \Sigma$
• $ϵ$: empty string
• empty set
• $R_1\cup R_2$, where $R_1$ and $R_2$ are regex
• $(R_1\circ R_2)$ where $R_1$ and $R_2$ are regex
• ($R_1^{\star }$) where $R_1$ is a regex

Connection to Finite Automata §

[!math|{“type”:“theorem”,“number”:“auto”,“setAsNoteMathLink”:false,“_index”:1}] Theorem 2. A language is recognized by a FA $⟺$ $L$ is described by a ^a8210c.

\begin{proof} $⟹$ (L is recognized if L is described by regex): By the rules of what a regex is by definition, we can see that the regex can describe transitions through a NFA.

$⟸$ (L is described by regex if L is recognized): For a FA $M$, we can construct a GNFA:

[!math|{“type”:“definition”,“number”:“auto”,“setAsNoteMathLink”:false,“title”:“Generalized NFA”,“label”:“generalized-nfa”,“_index”:2}] Definition 3 (Generalized NFA). A NFA that has transitions in the form of regex.

Notice that for a 2-state GNFA with just a start and accept state with transition $R$ (some regex), we have proven that the recognized language can be expressed by regex.

Now, we prove that $k$-state GNFA $G$ can be reduce to 2 states by simply ripping out every intermediate state by replacing regex transitions with a more robust one. Let $q_i,q_j,q_r$ be 3 states in $G$, with transitions $R_1:q_i\to q_r,R_2:q_r\to q_r,R_3:q_r\to q_j,R_4:q_i\to q_j$. Then, we can rip $q_r$ by setting the transition $q_i\to q_j$ with $(R_1)(R_2^{\star })(R_3)\cup R_4$. \end{proof}

Non Regular Languages §

[!math|{“type”:“lemma”,“number”:“auto”,“setAsNoteMathLink”:false,“title”:“Pumping Lemma”,“label”:“pumping-lemma”,“_index”:3}] Lemma 4 (Pumping Lemma). For all regular languages $L$, there is a pumping length $p$ s.t. for all words $w=xyz$ with $|w|>p$,

1. $w=x{y}^{i}z\in L$ for all $i\ge 0$
2. $|y|>0$
3. $|xy|<p$

We can prove a language is non-regular by

1. assume $L$ is regular
2. must exist pumping length $p$
3. select string $w\in L$ of length $\ge p$
4. no matter how you write $w=xyz$ satisfying rules 2 and 3, pumping $y$ cannot give string in $L$
5. profit