Home, RSS feed

Models of Computation | Lecture Notes 4

2016 September 09. Friday.

What is this?

Fall 2016, University of Kentucky, Models of Computation, CS 575, with Dr Goldsmith. These incomplete lecture notes are just my own, not proofread or edited by Dr G or anyone else, so watch out for errors. If you see one then leave a comment or email me.

Algorithm to Turn a DFA into a Regular Expression

Remember or look up deterministic finite automatons (DFA’s), nondeterministic finite automatons (NFA’s), and regular expressions. Today we invent a new finite automaton, the generalized nondeterministic finite automaton (GNFA). It’s like an NFA except a transition arrow can also be labeled as any regular expression.

We’ll use this invention to prove that you can turn any DFA into a regular expression. (“Turn into” means that the regular expression will generate exactly the same strings that the automaton returns accept on.)

Let’s do an example. This is taken from chapter 1 of Theory of Computation by Sipser. Look at this DFA:

DFA Regex 1

First, make two new states, s and a. Second, make s the new start state and draw an \(\epsilon\) arrow from it to the old start state. Third, turn all the old accept states into reject states, and draw an \(\epsilon\) arrow from each of them to s, and make s an accept state. In this example we only had one original accept state. Fourth, replace all arrows with their regular expression form. In this example, that’s just the a, b arrow turning into an a U b arrow.

DFA Regex 2

Pluck state number 2, reconnect what’s left behind, and adjust the arrow labels to compensate:

DFA Regex 3

Now pluck state number 1 fill back in:

DFA Regex 4

Now we have a regular expression.

In general, the algorithm works like this and can turn any DFA into a regular expression:

  1. Initial setup. Add s and a. Shift the accept states and start state. Make the arrow labels look like regular expressions.
  2. Pluck off each state one by one and each time fill back in the arrows where you need to.

Last lecture you had an exercise that showed you can turn any regular expression into a DFA. Combining that with this, we now know that regular expressions and DFA’s are completely equivalent.

Step back and look at what we’ve done. Languages, DFA’s…

This has been our first major chunk in Models of Computation.

Now we know that regular languages and DFA’s are the same. This is our first major result. Get ready for more as the class goes on.

Properties of Regular Languages

(This is also stated “The class of regular languages is closed under complement.”)

Why?

Well if \(L\) is regular, then there is a DFA that accepts exactly \(L\). If I copy that DFA but make all the reject states into accept states and make all the accept states into reject states, then my new DFA will accept everything but \(L\).

Here is a DFA that accepts L = ((a U b) b* a)*:

simple DFA

Here is a DFA that accepts \(\bar L\)

DFA inverse

Note that flipping the accept and reject states works for a DFA but not for an NFA. I encourage you to do an example or two and see why not.

The class of regular languages is also closed under

Note that the last one, intersection, isn’t trivial. We’ve seen union using epsilons in an NFA, but intersection requires you to cross-product two DFA’s.

Sidenote: The Pigeon Brain Principle

If you are in an elevator with n people, and m > n buttons have been pushed, then at least one person pushed at least two buttons.

Mathematically, we say a function

can never be one-to-one.

So, if you have a DFA with n states, and you give it a string of length m > n, then at least one state must be visited at least twice.

More generally, the pigeon brain principle is hugely useful in mathematics and many major theorems rely on it.

Exercise

Look at this language:

Is it regular? If it is then draw me the DFA. If it’s not then explain why not.

And that’s lecture.

Public Domain Dedication.