Finite Automata

• state: circle
  • start state: has a arrow from nowhere
  • accept state: double circles
• transition: arrow

Input: finite string

Output: Accept or Reject

Language of Machine

---

• $Q$: finite set of states
• $\Sigma$: finite set of alphabet symbols
• $\delta$: transition function
• $q_0$: start state
• $F$: set of accept states

String and languages

• A String is a finite sequence of symbols in $\Sigma$
• A language is a set of strings (finite or infinite)
• The empty string $\epsilon$ is the string of length 0
• The empty language $\empty$ is the set with no strings

Defn: $M$ accepts string

Recognizing languages

• $L(M)=\{w|M accepts w\}$
• $L(M)$ is the language of M
• M recognizes $L(M)$

regular languages

Defn: A language is regular if some finite automation recognizes it.

regular languages

regular expressions

regular operations: Let A, B be languages

• Union: $A\cup B=\{w\in A \or w\in B\}$
• Concatenation: $A\circ B=\{xy|x\in A \and y\in B\}=AB$
• Star: $A^*=\{x_1...x_k|each\space x_i\in A\space for\space k\ge0\}$

Regular Expressions

• Built from $\Sigma$, members $\Sigma$, $\empty$, $\epsilon$ [atomic]
• By using $\cup,\circ,*$ [composite]