2. DFAs
Jan 13, 2022
Deterministic Finite Automata
1 | |
- for every state there is a transition for every symbol, in the alphabet
- machine cannot change memory, only read from it
- to accept: all input is scanned and last state is accepting
- to reject: all input is scanned and the last state is non-accepting
Formal definition
- \(M = (Q, \Sigma, \delta, q_0, F)\) where
- \(Q\) is set of states
- \(\Sigma\) is input alphabet and \(\epsilon \notin \Sigma\) (never contains empty string)
- \(\delta\) is transition function
- \(q_0\) is initial state
- \(F\) is set of accepting states (0 or more)
Transition function
- \(\delta: Q \times \Sigma \rightarrow Q\)
- describes the result of a transition from state \(q\) with symbol \(x\): \(\delta(q, x) = q'\)
-
can be represented as a transition table, for example:
\(\delta\) a b \(q_0\) \(q_1\) \(q_2\) \(q_1\) \(q_0\) \(q_2\) \(q_2\) \(q_2\) \(q_0\)
Extended transition function
- \(\delta^*: Q \times \Sigma^* \rightarrow Q\)
- \(\delta^*(q, x) = q'\)
- describes the resulting state after scanning string \(w\) from state \(q\)
- example: \(\delta^*(q_0, abbba) = q_2\)
- special case, for any state q: \(\delta^*(q, \epsilon) = q\)
- in general: implies there is a walk of transitions \(w = \sigma_1\sigma_2...\sigma_k\) from q to q'
Language accepted by DFA
- \(L(M)\) denotes and contains all strings accepted by M, i.e. M recognizes \(L(M)\)
- for a DFA, \(M = (Q, \Sigma, \delta, q_0, F)\) => \(L(M) = \{ w \in \Sigma^*: \delta^*(q_0, w) \in F \}\)
- language rejected by M: \(\overline{L(M)} = \{ w \in \Sigma^*: \delta^*(q_0, w) \notin F \}\)
- language L is regular is there is a DFA M that accepts it \(L(M) = L\)
- the languages accepted by DFAs form the family of regular languages