Regular Expressions


def. Automata is an abstract model of a computer.

def. Regular Language is a language that can be expressed by a FSM

def. Trap state is a state in which any symbol input leads to the same state.

def. Closure of is simply the set of states reachable from with only .

Deterministic Finite Automata (DFA)

[= Finite State Machine]

  • is the set of all states
  • is the set of all symbols
  • is a function mapping from current state to the next state
    • [= empty strings lead to itself]
    • where is a single symbol [= processes only one per tick]
  • is the start state (entry point)
  • is the set of final states


def. Language. A string is accepted by a DFA when:

  1. After processing the string, the DFA is in a final state
  2. The string is in the language

The set of all aceepted strings by a DFA is the language of the DFA:

i.e. all the strings which, after processing it thru , it lands on a final state

Non-deterministic Finite Automata (NFA)

def. Non-deterministic Finite Automata can have multiple edges with the same labels; i.e.

i.e. from the current state, you can go to multiple states.

Example Non-deterministic FSM


corr. “there exists a walk between whose labels concatenate to ” is equivalent to:

thm. All NFA can be convered into a DFA which:

Proving Regularity after Applying Properties

e.g. let be a regular language. For all strings in replace one with , and let this new language . Is this a regular language?

pf. let be a DFA for .

  1. Make a copy and enclose it in a new machine,
  2. For all arcs in write a arc to the corresponding destination state in .
  3. The start state for is start state.


Now, let

  • , and where
  • , , as we outlined above
  1. If then

→ proofs often involve duplicating the machine in some way.

DFA Minimization