Finite Automata (Finite memory/states)

• States are switched by reading input symbols
• Initial state has the arrow pointing to it
• Final state has two circles around it

DFSM (Deterministic Finite Automata):

• K is a finite set of states
• $\Sigma$ is an alphabet
• $s \in K$ is the initial state
• $A \subseteq K$ is the set of accepting (final) states
• $\delta$ is the transition function from ($K \times \Sigma$) to $K$

$\delta: K \times \Sigma \rightarrow K$

$\delta(p, a) = q : p \frac{a}{\rightarrow} q$

Accepting by a DFSM:

• Basically when you read the string w iff reading M ends at the final state then the string w is accepted, else it is rejected.
• The language accepted by M, L(M), is the set of all strings accepted by M.
• Also no $\epsilon$ transitions and no choice

Drawing Example

TBA from prof example notes

Symbols Example

TBA from prof example notes

Theorem: Every DFSM M, on input s, halts in $|s|$ steps.

Example:

Regular Languages

A language is regular iff it is accepted by some FSM.

Examples:

$L = \{w \in \{a, b\}^{*} : \text{every a is immediately follow by a b}\}$

$L = \{w \in \{0, 1\}^{*} : \text{w has odd parity}\}$

$L = \{w \in \{a, b\}^{*} : \text{w contains at most b}\}$

---

When the starting state IS the final state, then that means you are accepting $\epsilon$

This also means that $\epsilon$ is accepting (in the language)

So basically a iff relationship

---

$L = \lbrace{w \in \lbrace{a, b\rbrace}^{*} : \text{no two consecutive characters are the same}\rbrace}$

$L = \{w \in \{a, b\}^{*} : \text{every a region in w is of even length}\}$

$L = \{w \in \{a, b\}^{*} : \text{every b in w is surrounded by a's}\}$

---

Therefore, DFSMs are complete since their transition functions are always complete (So any missing transitions lead to the "dead" state - even if it is not shown for clarity)

Programming FSMs

In this example we want to cluster strings that share a "future"

$L = \lbrace{w \in \lbrace{a, b\rbrace}^{*} : \text{w contains an even number of a's and an odd number of b's}\rbrace}$

$L = \lbrace{w \in \lbrace{a - z\rbrace}^{*} : \text{all five vowels, a, e, i, o, and u, occur in w in alphabetical order}\rbrace}$

$L = \lbrace{w \in \lbrace{a, b\rbrace}^{*} : \text{w does not contain the substring aab}\rbrace}$

• It is easier to construct the DFA for $L = \lbrace{w \in \lbrace{a, b\rbrace}^{*} : \text{w contains aab}\rbrace}$
• So start with $\neg L$ and complement it

$\neg L$:

How to complement:

Just flip the accepting and rejecting states

L:

The Missing Letter Language

Let $\Sigma = \lbrace{a, b, c, d\rbrace}$

Let $L_{\text{Missing}} = \lbrace{w : \text{there is a symbol} \ a_{i} \ \in \Sigma \ \text{not appearing in} \ w\rbrace}$

Trying to make a DFSM for $L_{\text{Missing}}$ is super difficult but apparently making a NDFSM) (Non-deterministic FSM) is easier.

See The Missing Letter Language NDFSM

NDFSM (Non-Deterministic Finite State Machine)

• K is a finite set of states
• $\Sigma$ is an alphabet
• $s \in K$ is the initial state
• $A \subseteq K$ is the set of accepting states
• $\Delta$ is the transition relation. It is a finite subset of $(K \times (\Sigma \cup \{\epsilon\})) \times K$
  • No longer a function because from the same state the same input, you can get to different states

Accepting by an NDFSM:

• Basically M accepts a string w iff there exists some path along which w drives M to some element of A.
  • In English, w is accepted if it moves the initial state to literally any of the possible accepting states
  • So if all are rejecting then you reject w (w is NOT in L(M))
• The language accepted by M, L(M), is the set of all strings accepted by M.

Optional Substrings

$L = \lbrace{w \in \lbrace{a, b\rbrace}^{*} : \text{w is made up of an optional a followed by aa followed by zero or more b's}\rbrace}$

$L = \lbrace{w \in \lbrace{a, b\rbrace}^{*} : \text{w = aba or |w| is even}\rbrace}$

For or, split the branch/path and use $\epsilon$ as the transition symbol on both paths as the or is the inclusive or.

The Missing Letter Language NDFSM

Let $\Sigma = \lbrace{a, b, c, d\rbrace}$

Let $L_{\text{Missing}} = \lbrace{w : \text{there is a symbol} \ a_{i} \ \in \Sigma \ \text{not appearing in} \ w\rbrace}$

Now it is easier:

$L = \lbrace{w \in \lbrace{a, b, c\rbrace}^{*} : \exists{x, y} \in \lbrace{a, b, c\rbrace}^{*} \ (\text{w} = \text{x abcabb y})\rbrace}$

Pattern Matching using a DFSM:

Pattern Matching Using an NDFSM:

Analyzing Nondeterministic FSMs

You can do this in 2 ways:

• Explore a search tree
• Follow all paths in parallel
  • You can use sets of states instead of just states which makes it DETERMINISTIC

Dealing with Epsilon Transitions

Simulating a NDFSM

Example:

NDFSM and DFSM

So clearly: $\{\text{Languages accepted by a DFSM}\} \subseteq \{\text{Languages accepted by a NDFSM}\}$

Theorem 5.3: For each NDFSM, there is an equivalent DFSM

• NFA are Easy to Build while
• DFA are Easy to Use

So build an NFA FIRST, and then make it an DFA

Finally, we can use this algorithm to Construct a DFSM from a NDFSM:

1. Compute the $eps(q)'s$
2. Compute $s' = eps(s)$
3. Compute $\delta'$
4. Compute $K' = \text{a subset of} \ \mathcal{P}(K)$
5. Compute $A' = \lbrace{ Q \in K' : Q \cap A \neq \emptyset \rbrace}$

Hard Example to complete: