Finite Automata

Highschool assignment on this stuff for historical purposes :)

Regular Languages

An alphabet is denoted as $\Sigma$, and ${\Sigma }^{\ast }$ is the set of all strings formed with $\Sigma$
We denote a language as $L\subseteq {\Sigma }^{\ast }$
The power set (the set of all subsets) of ${\Sigma }^{\ast }$ is denoted as $2^{{\Sigma }^{\ast }}$, so $L\in 2^{{\Sigma }^{\ast }}$

Regular languages are languages that can be determined by deterministic finite automata
DFA are good models for machines with extremely limited memory
A finite automaton is a 5-tuple $(Q,\Sigma ,\delta ,q_0,F)$,

• $Q$ is a finite set of states
• $\Sigma$ is a finite alphabet
• $\delta :Q\times \Sigma \to \Sigma$ is a transition function
• $q_0$ is a start state
• $F$ is a set of accept states

The finite automaton determines a language $L\subseteq {\Sigma }^{\ast }$ if only “processing” a string (and all strings) $x\in L$ results in an accept state $\in F$. This is a fairly self-explanatory process, we start at $q_0$ and repeatedly run the transition function over the next symbol in $x$.

A non-deterministic finite automata (NFA) can be in multiple states at once. Funky!
Additionally, a state can lack a transition for a symbol, or even transition without a symbol ($ϵ$)

The NFA computes like the multi-verse (it follows all different possibilities in parallel). This can be viewed as guessing the future, and then verifying it as the rest of the input is read in. If a machine’s guess is not verifiable, it dies! If any copy is in an accept state, then the string is accepted.

An NFA is still a 5-tuple $(Q,\Sigma ,\delta ,q_0,F)$, but now $\delta :Q\times {\Sigma }_{ϵ}\to Q^{\ast }$ where ${\Sigma }_{ϵ}=\Sigma \cup \{ϵ\}$ ($Q^{\ast }$ is sometimes written $\mathcal{P}(Q)$)

Interestingly, NFAs have the same computational power as DFAs. That is, any NFA can be converted to a DFA. However, they let you express a lot of interesting languages more concisely, so it’s a good showcase of the power of DFAs.

This isn’t as strange as it sounds. Our DFA will have a state for every possible subset of states in our NFA, with a transition function modified appropriately. Of course, this will not necessarily be the minimum DFA for the language (on the contrary).

We say regular languages are closed under three regular operations,

1. $A\cup B$
2. $A\circ B$
3. $A^{\ast }$

These aren’t too difficult to see. These regular operations help us show other closure properties,

• $\bar{A}$ (use $\bar{F}$)
• $A^R$ (start at each of the end states, flip the transitions)
• $A\cap B$ (construct with De Morgan’s law)

Non-Regular Languages

Given a language $L$, how do we check it is not regular? Having trouble constructing a DFA is not sufficient…

Let $D$ be a DFA with $n$ states. Any string $w$ that has length at least $n$ must visit some state more than once. That means the substring of $w$ between a revisited state can be removed or multiplied without changing the string’s acceptance.

In other words, for any regular language $L$, there is a pumping length $p$, such that for any string $w\in L$, where $|w|\ge p$, we can write $w=xyz$ with $|xy|\le p$, $|y|\ge 1$, and $x{y}^{i}z\in L$ for all $i$

So to show something is not a regular language, we show that we can break the pumping lemma for any choice of $p$, as a proof by contradiction.

Example:
Assume $L$ is regular and let $p$ be the pumping length. Consider the string $w=0^p{1}^p$.

Because $w\in L$ and $|w|\ge p$, the pumping lemma guarantees that $w$ can be split into $3$ pieces $w=xyz$ such that $|xy|\le p$, $|y|\ge 1$, and $x{y}^{i}z\in L$ for all $i$.

But since $|xy|\le p$, $y$ consists solely of $0s$, we have $x{y}^{i}z=0^{p+i-1}{1}^p\notin L$