Finite State Machine
Finite Automata
“One way to define a language is to construct an automaton—a kind of abstract computer that takes a string as input and produces a yes-or-no answer. The language it defines is the set of all strings for which it says yes.
Formal Language - A Practical Introduction by Adam Brooks Webber
a. Deterministic Finite Automata (DFA)
DFA $M = (Q, \Sigma, \delta, q_0, F)$, dimana:
- $Q$ adalah set semua state (finite),
- $\Sigma$ adalah alfabet/ input (finite set symbols),
- $\delta \in (Q xx \Sigma \to Q)$ adalah fungsi transisi,
- $q_0 \in Q$ adalah start state,
- $F \subseteq Q$ adalah set state final (accepting state).
Contohnya: $Q = {A, B}$, $\Sigma = {a, b}$, $F = {B}$ dan $\delta$ = + $\delta(A, a) = B$ + $\delta(A, b) = A$ + $\delta(B, a) = B$ + $\delta(A, b) = A$
digambarkan dengan:
String $x \in \Sigma^{\ast}$ akan di terima oleh DFA $M = (Q, \Sigma, \delta, q_0, F) \iff \delta^{\ast}(q_0, x) \in F$.
Untuk DFA $M = (Q, \Sigma, \delta, q_0, F)$, $L(M)$ adalah language yang bisa diterima oleh $M$, di mana $L(M) = {x \in \Sigma^{\ast} | \delta^{\ast}(q_0, x) \in F}$.
Regular language adalah language yang diterima oleh sebuah finite automata, atau sebuah regular language adalah $L(M)$ untuk suatu DFA $M$.
Regular operation adalah operasi pada language. Misalnya A dan B adalah language, maka operasinya:
- union, $A \cap B = {x | x \in A or x \in B}$,
- concatenation, $A \cdot B = {xy | x \in A and y \in B}$,
- star, $A^{\ast} = {x_1, x_2, \cdots, x_k | k \geq 0, \forall x_i \in A}$.
Sifat rl:
closed under complement, jika $L] adalah language dari $\Sigma], maka komplemen dari $L$, $\overline{L} = {x \in \Sigma^{\ast} | x \notin L}$, jika $L$ adalah regular language, maka $\overline{L}$ juga adalah regular language.
closed under intersection, jika $L_1$ dan $L_2$ adalah language, intersection (irisan) dari $L_1$ dan $L_2$ adalah $L_1 \cap L_2 = {x | x \in L_1, x \in L_2}$, jika $L_1$ dan $L_2$ adalah regular language, maka $L_1 \cap L_2$ juga adalah merupakan regular language.
closed under union, jika $L_1$ dan $L_2$ adalah language, union (gabungan) dari $L_1$ dan $L_2$ adalah $L_1 \cup L_2 = {x | x \in L_1 \text{atau} x \in L_2, \text{atau keduanya}}$, jika $L_1$ dan $L_2$ adalah regular language, maka $L_1 \cup L_2$ juga adalah merupakan regular language.
b. Nondeterministic Finite Automata (NFA)
NFA $M = (Q, \Sigma, \delta, q_0, F)$ dimana:
- $Q$ adalah set semua state (finite),
- $\Sigma$ adalah alfabet/ input (finite set symbols),
- $\delta \in (Q \times (\Sigma \cup {\epsilon}) \to P(Q))$ adalah fungsi transisi,
- $q_0 \in Q$ adalah start state,
- $F \subseteq Q$ adalah set state final (accepting state).
Contohnya: $Q = {q_0, q_1, q_2}$, $\Sigma = {a, b}$, $F = {q_2}$ dan $\delta$ =
$\begin{aligned} \delta(q_0, a) & = {q_0, q_1} \\ \delta(q_0, b) & = {q_0} \\ \delta(q_0, \epsilon) & = {q_2} \\ \delta(q_1, a) & = {} \\ \delta(q_1, b) & = {q_2} \\ \delta(q_1, \epsilon) & = {} \\ \delta(q_2, a) & = {} \\ \delta(q_2, b) & = {} \\ \delta(q_2, \epsilon) & = {} \end{aligned}$
digambarkan dengan:
conver NFA to DFA
lorem
minimization of DFA
Myhill Nerode Theorem for minimization DFA