Week 5 - DFAs

What is a string?

A finite length sequence of elements in an alphabet

What is a DFA made up of?

A finite set of states
An alphabet
A set of initial states that is in the set of all states
A set of accepting states which is in the set of all states
A transition function

What is the union theorem?

Given two languages L1 and L2, the union of these languages is any word that is in either of these languages

How do we prove the union theorem?

Create two automata A1 and A2, where A1 accepts L1 and A2 accepts L2.

Then construct another automaton such that it recognises both L1 or L2, set of its states is cross product of the automata so these states are pairs of states in A1 and A2

Then construct a transition function where the accepting states are the pairs (q1, q2) where q1 is accepted by A1 or q2 is accepted by A2

What is a regular operation?

An operation on regular languages that has a result result

What are examples of regular operations?

Intersection, union, reverse of an automaton, complement, repetition, sequence

What is the pigeonhole principle?

Given n boxes and M > N objects, at least one box must contain more than one object