Finite Automata
A deterministic finite automaton is a structure
$M=(Q,\Sigma, \delta, s, F)$
A language is regular if it is accepted by a DFA.
Closure properties
Regular sets are closed under:
1. Union: $A\cup B = \{x | x\in A \text{ or } x\in B\}$
2. Intersection: $A\cap B = \{x | x\in A \text{ and } x\in B\}$
3. Concatenation: $AB=\{xy| x\in A, y\in B\}$
4. Asterate: $A*=\{x_1x_2\ldots x_n | x_i\in A \}$
5. Complementation: $A^c=\{x|x\notin A\}$
Comments
Post a Comment