Regular Languages

Deterministic Finite Automata

A deterministic finite automaton is a 5-tuple

• , a finite set of states
• , a finite alphabet
• , the transition function
• , the start state
• , the accept states

is the set of strings recognized / accepted by . is in iff there is a sequence of states such that , for and

Nondeterministic Finite Automata

Define , where represents an empty string

A nondeterminstic finite automaton is a 5-tuple

• , a finite set of states
• , a finite alphabet
• , the transition function
• the start state
• the accept states

Given a string , we can write where . This string is accepted by iff there exists a sequence of states such that , for , and

Every NFA has an equivalent DFA over the states and appropriately constructed transitions.

Regular Expressions

A language is regular if it is recognized by some DFA

Given languages and , the regular operations are as follows

• union
• concatenation
• star

Regular languages are closed under these operations.

A regular expression over is an object of the following type

A language is regular if it can be expressed by a regular expression.

Generalized Nondeterministic Finite Automata

A generalized nondeterministic finite automata is a 5-tuple , where

• is a finite set of states
• is a finite alphabet
• is a transition function, and is the set of all regular expressions over
• is the start state
• is the accept state

A GNFA accepts a string if where and there is a sequence of states such that is the start state, is the accept state, and

Define a procedure to reduce the number of states in a GNFA

1. Let be the number of states of
2. If , then there is a start and end state connected by an arrow. Return the regex of this arrow
3. If , pick any such that and let be a GNFA where , and for all , ,
4. Compute and return

Pumping Lemma

If is a regular language, then there is a number (the pumping length) where if with , then can be divided into 3 pieces where

1. for ,

The proof for this uses the pidgeon hole principle to show that for a DFA with states, a string with length greater than must repeat one of these states, and thus yields the string .

This tool is used to show that languages are not regular.