Bob: You’ve transformed yourself into a computer tech. The analogy of finite automata you provided was absolutely fantastic. I’m sure you wouldn’t mind if we delved deeper into finite automata, right?
Alice: go ahead, please.
Bob: Anything starts with its name, right? The first introduction of anything is its name, right?
Alice: I agree, sir. My name is Alice, and I am human.
Bob: Correct, name decides the definition, so first we have to understand the definition. A formal definition of finite automata, right?
Alice: Totally right. Then, what is the formal definition of finite automata?
Bob: So, the definition of finite automata is divided into chunks, or we can say that it divides into sets.
Alice: Means, as we merge them, we get the finite automata, right?
Bob: Totally, let me clarify for you. Finite automata have rules for going from one state to another, so we have a set of rules. These rules depend on the input. So, we have set of inputs. For example, we can use the example of a light switch again. The rule of the light bulb turning off and on depends on the switch, and the switch state, decides the state of light bulb or we can say switch current state, decides the state of the light bulb, right?
Alice: Right, Input is deciding the state and state is binding the rule means if when the switch will turn off the light bulb will be off its rule.
(Then Alice concludes)
Alice: So, rules, states and inputs are interlinked.
Bob: Absolutely, rules are related to states and these rules depends on the input.
(Then Bob adds an statement by continuing his previous statement)
Bob: This input is part of a set of inputs. Such as this light switch scenario, we have a set of inputs which have two inputs: on and off, right? So, we can say on and off belong to this set. We call this set Alphabet.
Alice: yeah, ON is an input and OFF is an input both making a group of input, and we are calling it a set of input, and this set is Alphabet.
Bob: Correct, and then Finite automata have a start state and a set of end states, which we can say are accept states.
Alice: so, we have states, rules, inputs, starting state and end states which we are calling accept states right.
(Bob says with smile)
Bob: So, what will be the formal definition of finite automata, The formal definition will be a finite automaton is a list of those five objects: set of states, input alphabet, rules for moving, start state, and accept states. In mathematical language, a list of five elements is often called a 5-tuple.
5-tuple (Q, Σ, δ, q0, F)
1. Q is a finite set called the states,
2. Σ is a finite set of inputs called the alphabet,
3. δ : Q × Σ−→Q is the transition function,
4. q0 ∈ Q is the start state, and
5. F ⊆ Q is the set of accept states.
Alice: Okay, these five ‘musketeers’ come together to define finite automata.
Bob: Hahhaha, you can say that.
Alice: But here in δ(Delta) is a transition function would you please explain its function please. How it's working.
Bob: OfCourse!!
Top comments (0)