Computational Model: Idealized model of a computer.
- Real computers are complicated, so this makes mathematical theory manageable.
Finite Automaton: A set of states and rules for going from one state to another, depending on the input symbol. Has a start state and a set of accept states.
Formal Definition: A finite automaton is a 5-tuple consisting of:
Example Transition Function (\delta):
\delta(x,1) = y “If the automaton is in state x when it reads a
1, move to state y.”
State Diagram: Diagram of finite states and events.
Example: Formal description of a finite automaton
M_1 = (Q, \Sigma, \delta, q_1, F), where
- Q = \{ q_1, q_2, q_3 \}
- \Sigma = \{ \texttt{0, 1} \}
- \delta is described as
01q_1 q_1 q_2 q_2 q_3 q_2 q_3 q_2 q_2
- q_4 is the start state
- F = \{ q_2 \}
Note: On Language
If A is the set of all strings that machine M accepts, we say that A is the language of machine M.
L(M) = A
- “M recognizes A”
A machine may accept several strings, but it always recognizes only one language.
- If it accepts no strings, it still recognizes one language, the empty language.
When designing finite automata, think through test strings and possibilities like you are the machine.
Union
A \cup B = \{ x | x \in A \text{ or } x \in B \}
Concatenation
A \circ B = \{ xy | x \in A \text{ and } y \in B \}
Star
A* = \{ x_1 x_2 ... x_k | k \ge 0 \text{ and each } x_i \in A \}
Note: Unlike union and concatenation, start is a unary operation, not a binary operation.
Example:
Let \Sigma be the standard 26 letters a—z. If A = \{ \texttt{good, bad} \} and B = \{ \texttt{puppy, girl} \}, then:
A \cup B = \{ \texttt{ good, bad, puppy, girl} \}
A \circ B = \{ \texttt{ goodpuppy, goodgirl, badpuppy, badgirl } \}
A* = \{ \epsilon, \texttt{ good, bad, goodgood, goodbad, badgood, badbad, goodgoodgood, goodgoodbad, goodbadgood, goodbadbad, ... } \}
Suppose we want to combine two DFAs the recognize:
L_1 = \{ w | w \text{ has even number of 1s } \} \\ L_2 = \{ w | w \text{ has two 1s } \}
The individual machines are:
It is beneficial to think through the machine as the states
Regular Language: A class of languages that can be recognized by finite automata.
Note: Things gone over in class that I haven’t bothered to sort into sections.
Observation: n-tuples
Cartesian coordinates are 2-tuples (x,y)
Q: How do represent all possible values?
A: \{ (x,y) | x \in R \land y \in R \}
or, (x,y) = R^2 = R \times R
We can increase the number of dimensions easily.
\begin{align*} \text{3D: } & \{ (x,y,z) | x \in R \land y \in R \land z \in R \\ &= R^3 \\ &= R \times R \times R \} \end{align*}
Observation: Finding every combination
Look at this 1-tuple:
B = \{0,1\} \\ b \in B
Q: Can we create 2D tuples from b?
A: Yes. (b_1, b_2) \in B^2
Creating a Language:
Recall: Languages are sets of strings.
B^2 = \{ (b_1, b_2) | b_1 \in B \land b_2 \in B \}
Q: How many unique 3-bit strings are there?
A: 2^3 = 8 possibilities
- This simple rule of counting, is just Cartesian product, we are counting tuples.
Q: How many unique strings can use make using up to 3-bits?
A
B^3 \cup B^2 \cup B^1 \cup B^0
Note: B^0 is an empty string (\{ \epsilon \})
- Remember that empty string is \ne empty set! (|B^0| = 1)
Rewriting the above statement as a formula:
\cup_{i = 0}^3 B^i = B^3 \cup B^2 \cup B^1 \cup B^0
Q: Now, how do you represent all binary strings?
A: \cup_{i = 0}^\infin B^i
Note: More shorthand
B^* = \cup_{i = 0}^\infin B^i
We just basically big-banged a language from the alphabet B.
How do you Process Formal Languages?:
How do you handle a seemingly infinite number of strings with a machine?
Formal Languages: Languages that are perfectly generated by forms.
- e.g., Python
Emergent Behavior: Simple rules can create complex behavior.
Our alphabet is B = \{ \texttt{0,1} \}
Our language is L=\{ s | s \in B^* \land |s| = 2k, \exists k Z\}
Cardinality of \phi:
Cardinality of Combining DFAs: