1. DFAs and NFAs

Introduction

Definitions

• Alphabet, $\Sigma$: set of symbols. $\Sigma \neq \emptyset$
• String: sequence of symbols. $\epsilon$ = empty string
• $\Sigma^*$: set of all strings
• Language $L$: subset of $\Sigma^*$

Concatenation

Strings

$xy$ is y concatenated to $x$, where $x$ and $y$ are either strings or characters.

Concatenation of strings is associative: brackets are not needed.

Languages

i.e. A.map(a => B.map(b => a+b))

Language concatenation is associative.

$\{ \epsilon \}$ is the identity language: $\{ \epsilon \}A = A\{ \epsilon \} = A$.

Powers: Strings/Characters

$a^n$ is the string/character concatenated $n$ times

Base case: $a^0 = \epsilon \therefore a^{n+1} = a^n a$.

Powers: Languages

Thus, $A^*$ will always contain the empty string, while $A^+$ will only contain it if it is a member of $A$.

Properties

Deterministic Finite Automata

Where:

• $Q$ is a non-finite, empty set (vertices) of states
• $q_0$ is the start state (arrow from nowhere)
• $F \subseteq Q$ is the set of end states (double circle)
• $\Sigma$ is the input alphabet - a non-finite, empty set. Each symbol represents a transition. Every transition can occur at any state, even if it just loops back
• $\delta$ is the transition function: $Q \times \Sigma \rightarrow Q$ - a function taking the state and transition as inputs, and outputting an end state

$M$ reading the input string $w\in Z^*$ symbol by symbol. For each symbol, the transition function is run using with the current symbol and state. The input string is accepted if $M$ ends in an end state.

Extended Transition Function

$\hat{\delta}$ extends $\delta$ to take in strings (and not just symbols) as the transition by processing each symbol in the string and passing the remaining substring recursively.

• The string $w$ is accepted by $M$ if $\hat{\delta}(q_0, w) \in F$
• The language accepted by $M$, $L(M) = \{ w\in Z^* \mid \hat{\delta}(q_0,w)\in F \}$
• The language $A \in \Sigma^*$ is regular if $A = L(M)$ for some DFA $M$

All finite languages are regular (e.g. OR every single string) but not all infinite languages are regular.

Regular languages are closed over:

• Complement (inverse)
• Intersection
• Union
• Concatenation
• Star

Proving Regular Languages Are Closed under the Complement Operator

Let $A\subseteq \Sigma^*$ be regular. Show $\bar{A}$ is regular.

By their definitions, $A = L(M)$ for some DFA $M = (Q, \Sigma, \delta , q_0, F)$.

Swap accepting and non-accepting states:

Let $M' = (Q, \Sigma, \delta , q_0, Q - F)$. Now, show that $L(M') = \bar{A}$.

To do this, we first show that $M'$ is regular. This means that $L(M) = \{ w \in Z^* \mid \hat{\delta}(q_0, w) \in F \}$.

The first requirement, $w\in Z^*$ is obviously fulfilled. The second bit will be:

$Q-F$ is the complement of $F$, so: $\hat{\delta}(q_0, w) \notin F$

The definition of the extended transition function is $\hat{\delta}(q_0, w)\in F$, which is the complement of above. Thus, this means it satisfies the opposite of $L(M)$:

Intersection of Two Automata

Let $A, B \subseteq \Sigma^*$ be regular. Show that $A \cap B$ will be regular.

$A = L(M_1)$ for DFA $M_1 = (Q_1, \Sigma, \delta _1, q_1, F_1)$.

$B = L(M_1)$ for DFA $M_2 = (Q_2, \Sigma, \delta _2,q_2,F_2 )$

Only the alphabet is the same between the automata

Idea: keep track of the state $M_1$ is in and the state $M_2$ is in at the same time. Define the state as a pair of two states.

Now, we need to define the transition function where $a \in \Sigma$ is the transition symbol, $w \in \Sigma^*$ is the transition string, $p_1 \in Q_1$ and $p_2 \in Q_2$:

Need to show $L(M) = L(M_1) \cap L(M_2)$. For any string $w \in \Sigma^*$ where $w \in L(M)$:

Union of Two Automata

Let $A, B \subseteq \Sigma^*$ be regular. Show that $A \cup B$ will be regular.

$A \cup B \leftrightarrow \overline{\bar{A} \cap \bar{B}}$ by De Morgan’s law. There is closure under the complement and intersection, so there must be closure under the union operation.

Non-Deterministic Finite Automata

NFA: a state can have zero or multiple transitions using a single symbol.

$\delta: Q\times \Sigma \rightarrow P(Q)$, where $P(Q)$ is the power set. That is, the transition function will return a set of states. If multiple states are returned, $M$ can move to any of those states. If the empty set is returned, $M$ will get stuck and that route should be ignored.

If any route leads to an accept state, the string should be accepted.

Extended Transition Relation

That is, for every state it can be in, calculate the possible transition(s) for the next symbol, put them all in a set, and repeat until the input string is empty.

$w$ is accepted by $M$ if and only if $\hat{\delta}(q_0, w) \in F \neq \emptyset$.

The language accepted by $M$ is the set of all strings where the above is true:

NFDA to DFA Conversion Through Subset Construction

States become a set containing all states it could be in given the transitions. If it can be in the states $\{ q_x, q_y, q_z \}$ then denote the state as $q_{xyz}$. Accept all states where the set contains any element from the accept states set. Add a new reject state with a self-transition under all symbols to ensure that every state has transitions for every symbol.

Proving Every NFA is Accepted by a DFA

Idea: keep track of all states the NFA $M$ can be in while reading the input.

Subset automaton (DFA) $M' = (P(Q), \Sigma, \delta', \{ q_0 \}, F')$ where $F' = \{ S\subseteq Q \mid S \cap F \neq \emptyset \}$ (any state where one or more elements of the state contains an element from the accept states).

Now show that $L(M') = L(M)$. For any $w \in \Sigma^*$, if $w \in L(M')$:

The definition of $L(M')$: $\hat{\delta'}(\{ q_0 \}, w) \in F'$.

Hence, $w \in L(M)$.

NDFA with $\epsilon$-Transitions

Example use case: union of two regular languages: one new start state, with two $\epsilon$ transitions to each regular language.

$\epsilon$-closure of $q$: $E(q) = \{ p \in Q \mid p \text{ is reachable from } q \text{ with a sequence of } \epsilon \text{ transitions} \}$.

The sequence can be of length zero, or be arbitrarily long. Note that the $E(q)$ will always contain $q$.

To convert an NDFA with $\epsilon$-transitions to a DFA, run the same process as for NFAs:

• Replace each state by its $\epsilon$ closure
• Add state transitions to any state that is accessible from any member of the closure
  • $\sigma'(S, a) = \bigcup_{q \in S}{\bigcup_{p \in \sigma(q, a)}{E(p)}}$
• Replace the start state with $E(q_0)$

Extended Transition Relation