Regular Expressions and Deterministic Finite Automata generate the SAME sets of languages:

If a language can be expressed by a regular expression, there is a finite automaton that accepts it, and vice versa.

These are called "regular" or "Type 0" languages.

Alphabets are often represented with a Sigma (that fancy shape that's a cross between an E and  a backwards 3).  So Sigma is a set of characters that we call the alphabet.

Sigma* that means all strings generated from Sigma, or all possible strings over that alphabet.

If a Language L is regular, is the language Sigma* - L also regular?  Sigma*-L is the "complementary" language.  It consists of those strings not in L.  Think of how regular expressions work?  Think about how finite automata work?  If L is regular, do we know for a fact that Sigma*-L is also regular?

Let L be any regular language, and let F be the finite automaton that accepts that language.  Let F' be F accept that F' 's final states are the nonfinal states of F.  And F' 's nonfinal states are the final states of F.  So, where F has a nonfinal state, F' has a final state, and vice versa.

Any string accepted by F ends on a final state, so it ends on a nonfinal state in F'.  Any string not accepted by F ends on a nonfinal state in F, so it ends on a final state in F'.  So the strings accepted by F are precisely the strings not accepted by F'.  F' accepts the language of Sigma* - L.  So, this language must be regular.

UNION:

If two languages L,M are regular, is their union L U M also regular?

The union of two languages is the language of strings contained in either or both L or M.

Take the regular expression for L, the regular expression for M, and stick a | between them.


((0|2|3|4|5|6|7|8|9)*1(0|1|2|3|4|5|6|7|8|9)* ) |        ((0|1|2|3|4|5|6|7|8|9)*(0,2,4,6,8))

INTERSECTION:

If two languages L,M are regular, is their intersection also regular?

The intersection of two languages is the languages of strings contained in BOTH L and M.



A intersect B is the same thing as

Complement  ( Complement(A) U Complement (B) ) <== De Morgan's Law



If we have two regular expressions, and we want to see if they accept the same language:  We can convert them both to finite automata, reduce these automata, and see if they're the same.

Here's another way:

If L and M are two languages (or regular expressions), build the automata for L Intersect (Complement(M))  and for M Intersect (Complement(L)).  If BOTH are empty, then L=M.

The empty language has an automaton with exactly one state and it's a nonaccept state.


Mathematically, a Deterministic Finite Automaton can be thought of as a quintuple:  (Sigma,S,t,F,X)

Sigma is finite, nonempty set of characters:  an alphabet

S is a finite, nonempty set of states.

t is a transition function:  t:(S x Sigma) -> S.  (Given a state and a letter, there is exactly one state we can transition to.

F is a subset of S, it's the list of final (or accept) states.

X is an element of S; it's the start state.

A Nondeterministic Finite Automaton is also a quintuple (Sigma,S,T,F,X).

Sigma, S, F, X are all exactly the same.  The only difference is the T.

T is not a function.  It is a finite set of ordered triples:  S x Sigma* x S.

In a nondeterministic finite automaton, you can specify a node will jump to another node when it sees a certain STRING rather than a certain character.

And there might be more than one node that could be jumped to.