Skip to content

Latest commit

 

History

History
243 lines (183 loc) · 5.7 KB

01.md

File metadata and controls

243 lines (183 loc) · 5.7 KB
title
Regular Languages & DFA

Computational Model: Idealized model of a computer.

  • Real computers are complicated, so this makes mathematical theory manageable.

Finite Automata

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.

  • The simplest computational model.
  • Useful for attempting to recognize patterns in data.

Formal Definition: A finite automaton is a 5-tuple consisting of:

  1. Finite set of states ($Q$)
  2. Finite set for the alphabet ($\Sigma$)
  3. Rules for moving ($\delta$)
  4. Start state ($q_0 \in Q$)
    • There is only [one]{.underline} start state
  5. Set of accept states ($F \subseteq Q$)
    • The accept state(s) is a subset of all states

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

  1. $Q = { q_1, q_2, q_3 }$
  2. $\Sigma = { \texttt{0, 1} }$
  3. $\delta$ is described as
| | `0` | `1` | |-------|-------|-------| | $q_1$ | $q_1$ | $q_2$ | | $q_2$ | $q_3$ | $q_2$ | | $q_3$ | $q_2$ | $q_2$ |
  1. $q_4$ is the start state
  2. $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.

Designing Finite Automata

When designing finite automata, think through test strings and possibilities like you are the machine.

  • To check if you've got enough lines, remember that $|\delta| = |Q \times \Sigma|$

The Regular Operations

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 } } $$

  • Alphabet is ${ 0, 1 }$

The individual machines are:

It is beneficial to think through the machine as the states

Regular Languages

Regular Language: A class of languages that can be recognized by finite automata.

  • Regular languages are closed under union, concatenation, and star.

Proving a Regular Language

Assorted In-Class Activities

Note: Things gone over in class that I haven't bothered to sort into sections.

I

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

II

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}$

  • $s$ is in the set of all binary strings ($s \in B^*$),
  • and the length of $s$ is even ($|s| = 2k, \exists k Z$)

III

Cardinality of $\phi$:

  • $|\phi| = 0$
  • $|\phi *| = | { } * | = | { \epsilon } | = 1$

Cardinality of Combining DFAs:

  • Suppose $Q_1$ and $Q_2$ are states for two DFAs.
  • If you combine them into $Q_3$, $Q_3 \ne Q_1 \times Q_2$; some states may be unreachable or combined.