Lecture 16: More on Finite State Machines

Summary from last lecture

• Last time, we talked about representing FSMs via tables.
• We also discussed in some detail, NFAs introducing notions like $\epsilon$-transitions, massive parallelism, etc.

---

Alright... onto the new stuff.

The underlying topic for today is to discuss NFAs with more depth and compare/contrast them to DFAs. In other words, we'll see a striking equivalence of the two which will help us understand the regular languages with more depth (since we'll now have two different perspectives for looking at the same thing and adding another perspective is always useful).

• Every DFA can also be represented as an NFA (and vise versa).
  • Any language accepted by a DFA, can also be accepted by some NFA.
• Interestingly though, any NFA language can also be accepted by some DFA.
  • To see why, let us probe some thoughts via the following experiment.

Subset construction

Note that subset construction is also referred to as the powerset construction.

At brief high-level, I think the Wikipedia page for "Powerset construction" gives a nice definition:

Subset Construction:
The powerset construction or subset construction is a standard method for converting a nondeterministic finite automaton into a deterministic finite automaton which recognizes the same formal language.

Recall the tabular form of a DFA. From there, we can represent that table (also possible in software if you'd like) as we saw last lecture. We can perform a similar process with an NFA to form a table. From there on, we can also represent it through software and since we can form the table (see below) in the first place, we can represent the NFA as a DFA.

The key here is that we can assign "subsets" as states instead of just original singular states. See the conversion below.

First, we have our NFA:

Now we represent it via table:

And from this, we form our DFA:

(Note: see "Guide to Subset Construction" for more implementation details).

Philosophies of subset constructions

It is indeed the case that whatever you can do with an NFA, you can also do with a DFA. But as one might imagine, the amount of states and transitions in the DFA version of some NFA could be exponentially larger.

This fact helps use give clarity to the notion that one might suggest at this point: "Why would we build NFAs instead of DFAs if they both can represent the same language?". As stated above, they can be much more compact.

Moreover, certain things which we'll see later, are easier to worth with DFAs than NFAs and vise versa. See 37:00 from lecture for a good example.

An important result on regular languages

Recall from last lecture where we showed "A language $L$ is called a regular language if there exists a DFA $D$ such that $\mathscr{L}(D)=L$.". Since we just stated that NFAs are functionally the same as DFAs, we also can extrapolate the above theorem to this:

A language $L$ is called a regular language if there exists a NFA $N$ such that $\mathscr{L}(N)=L$.

So a regular language can now be thought of a language as an NFA or also a DFA. And to answer the philosophical question posed above, such a result means that we can work with NFAs instead (and vise versa) for certain problems which could lead to a new discovery/a new way of looking at things.

---

Properties of Regular Languages

Let us now discuss and probe some more properties about regular languages (RLs). We will toy around with some set theory operations by framing them as propositional logic connectives with languages as statements.

If $L_1$ and $L_2$ are regular languages, is $L_1 \cup L_2$?

Yes... just make an NFA with two $\epsilon$-transitions like so:

This is like the "or" case (existential).

If $L_1$ and $L_2$ are regular languages, is $L_1 \cap L_2$ as well?

This is like the "and" case and is also much harder to show than the "or" case. Let us try to see if this is true.

This is pretty interesting actually. We can indeed get the "and" case by applying De Morgan's Law to set theory. We can form "and" in propositional logic using just ~ and or via: ~(~p or ~q) which, in this context using languages and compliments, we get: $\overline{\overline{L_1} or \overline{L_2}}$

You might imagine that constructing some machine for this would be a multi-step process (e.g. lots of DFA-NFA, NFA-DFA conversions).

Concatenation

Works the same as you've seen in programming languages. If you have $w$ and $e$, the concatenated version is notated as $we$.

Note, some interesting properties which could be useful during manipulations:

• The empty string $\varepsilon$ is considered the identity element for concatenation
  $w \varepsilon=\varepsilon w=w$
• More so, concatenation is associative:
  $w \times y=w(x y)=(w x) y$

We can also perform concatenations over languages instead of just strings. Formally, we define concatenation over two languages$L_1$ and $L_2$ as:

Concatenation:
$\mathbb{L}_{1} \mathbb{L}_{2}=\left\{w_{X} \in \Sigma^{*} \mid w \in L_{1} \wedge x \in L_{2}\right\}$

This is, in some ways, like the cartesian product of two languages where $L_{1}L_{2}$ is "the set of all strings that can be made by concatenating string in $L_{1}$ with a string in $L_{2}$.".
You can also think of it as "The set of strings that can be split into two pieces: a piece from $L_{1}$ and a piece from $L_{2}$.". See 53:00 for more about the "splitting" intuition and an example use case. Briefly speaking, concatenating two automaton is like having each individual one complete some task, then the other would complete another task, then combine them together into one. We combine them by saying "do this, then do this".

Concatenating together two machines

Definitively, we can define a series of steps for concatenating together two machines:

1. Take the accepting states of machine 1, and draw $\epsilon$-transitions to the start state of machine 2.
2. Flip the accepting states in machine 1 to rejecting states.

Language exponentitian

We talked about how concatenation is almost like a "product". So consider some language $L$. We perform the concatenation of $L$ with $L$ to get $LL$. We can do it again to get $LLL$. And again: $LLLL$. Looks a little like exponentials in some sense right?

We have the following characteristics:

$L^{0}=\{\varepsilon\}$

and, inductively:

$L^{n+1}=L L^{n}$

---

The Kleene Star

We now introduce one more operation which is somewhat nuanced, but useful nonetheless:

Kleene Closure:
$L^{*}=\left\{w \in \Sigma^{*} \mid \exists n \in \mathbb{N}, w \in L^{n}\right\}$
which is mathematically equivalent to:

$w \in L^{*} \quad \leftrightarrow \quad \exists n \in \mathbb{N} . w \in L^{n}$

See 1:08 for a more detailed explanation. Briefly speaking, recall $\Sigma^{*}$. This is applying the same notion to languages (operating on strings instead of languages internally) via the notation $L^{*}$.

Closure properties

Remember how we defined closure properties in the previous lecture. Notice that we just examined a bunch of closure properties here.

If $L_{1}$ and $L_{2}$ are regular languages over an alphabet $\Sigma$, then so are the following languages:

• $\bar{L}_{1}$
• $L_{1} \cup L_{2}$
• $L_{1} \cap L_{2}$
• $L_{1} L_{2}$
• $L_{1} *$