Please enable JavaScript.
Coggle requires JavaScript to display documents.
Deterministic Finite State Automata - Coggle Diagram
Deterministic Finite State Automata
Deterministic Finite State Automata
finite automata
shortened version of finite state automata
FA = FSA
deterministic
state diagram
circle = state, line = transition, line with text = input causing transition(input condition), line with text leading to and from a single state = that state when supplied that input will lead back to that state, state that is "final" has double circle
transition = movement from one state to another
heat causes change of state in matter
final = accepted = accepted language
questions to ask when analyzing a state diagram
what are the possible ways to get to final?
what are the possible ways to NOT get to final state?
what are the symbols on lines? thats your alphabet
notes from analyzing this diagram
answer: all strings a,b that do not contain the substring aa
questions to ask when creating a state diagram
what cases must be satisfied and how do i test them
what boundary cases do i need to test for (ex: empty string)
start with diagrams you know to be correct, then determine if you can merge start states and final states
what set of strings does each state represent, if you dont know what set of strings would lead to a state, consider whther you need it or not
ex: given {01,101}∗ \n what do q1, q4, q5 represent?
q1 = strings starting with 01 and ending in 01, that may have an extra 0 (note the only symbol leading out is a 1), so as soon as it hits 1 it moves to next state, s0 {01,101}∗{0} \n
q4 = strings starting and ending with 101 that may have an extra 1 ( note the only symbol leading out is a 0), so as soon as it hits 0 it moves to next state, so {01,101}∗{1}
q5 = strings starting and ending with 101 that may have an extra 10,
the pattern is that each one can have as many repeating characters from previous transitions as they want, as long as they end in 01 or 101
deterministic finite automata
dfa = dfsa
deterministic = can only be in one state at a time
state = collection of information remembered by a system
state of the union is info about the us at that point in time
finite = only a finite number of possible states
Q
finite automata (FA) definition
FA = (Q,Σ,q0,A,δ)
Q = finite set of states
Σ = finite input alphabet(set of non-empty symbols
q0 = initial state, q0 ∈Q ( the initial state is a member of the finite set of states)
A = set of accepting states, A ⊆Q (A is a subset of the finite set of states)
δ = , the transition function
Q x Σ -> Q(each single state multiplied by each single input for each input leads to a state)
set multiplication, ex
{1,2,3} x {a,b} = {(1,a),(2,a),(3,a),(1,b),(2,b),(3,b)}
given Q={q0,q1,q2,0,1,2}\nΣ={0,1}\nδ would be $$\begin{array}{ } \n \\ & &\text{Starting State}\n\\\n \hline& & q0 & q1 &q2 & 0 & 1 & 2 \\ \hline \text{Input} & 0&q1&q2&q2&0&2&1 \\ \n &1&1&q2&q2&1&0&2 \\ \n\hline \end{array} $$
set of pairs(functions), {state+input,result),(state+input,result2),....}
the function (q0,0),q1) means\nstate q0 when given input 0 will lead to q1
the function (0,0),0) means \nstate 0 when given input zero will lead to 0\n
5-tuple
tuple = finite SEQUENCE of elements
5 tuple = sequence of 5 elements
same for nondeterministic, only difference is δ
for NFA, δ = Q X Q x Σ -> $$2^Q$$
only difference in definitions between deterministic and nondeterministic is that the functions for DFA can only have one function for each input and output pair, while nondeterministic can have more than 1 function per input and output pair
nondeterministic finite automata
deterministic vs nondeterministic
single thread vs multithread
nondeterministic = automata can be in multiple states at once
like shrodingers cat, the state can either be outcome A or B given a single input
