Teaching Talk by Dr. Inzemamul Haque on Deterministic Finite State Automaton

Consider the notion of a ‘formal language’. You might say, well, Latin and Sanskrit can be thought of as formal languages. While that is true, ‘formal language’ means something different when we enter the fields of computer science and logic. A ‘formal’ language has a set of ‘alphabet’ (or symbols that the language uses), and a set of ‘strings’ or what we can think of as words of the language. Like ‘afafba’ is technically composed of letters from the English language but is not a word in English, the set of words of a formal language can choose to include all such permutations or not include them.

Consider this formal language that I came up with. Let us call it binary2.0. According to me, the creator, binary2.0 is a language with the alphabet {0,1} and the permissible words in this language are the strings which have atleast two 1’s.

A formal language is said to be ‘regular’ if one can come up with a finite state automaton that satisfies the strings of the language. But what does any of that even mean?

Though the title of the talk sounds frightening, the concept of an automaton is simple. An automaton is a model of a machine that performs calculations by moving objects through “states”. States can be thought of as places or stages - there is a starting “initial” state and “final” states. If your object ends up in a final state, it is “accepted” and if it ends in a state that is not final, it is “rejected”. In the picture below, a state is represented by a circle.

In this image, we call the circle ‘A’ the initial state. This is because there is a first arrow leading into it. The stage ‘C’, circled twice, is the final state - this is the notation used to represent the final state. 

‘Finite’ means that there are countably many stages - that is, you can say definitively that there are five stages or some absurd number like ten thousand, seven hundred and fifty eight stages. You can still count to (though it might take you ages) ten thousand, seven hundred and fifty eight, thus implying that an automaton with those many states is finite. ‘Deterministic’ just means that every object that will end up in some state. Thus, Deterministic Finite State Automata (henceforth called DFA) are just models of machines which have finitely many states and perform computations on some objects. 

But, in our diagram, what are those arrows in between states? Well, we call them transitions. Let us continue with our formal language binary2.0. Consider the string 01101. 

First, we start on A. Note that the first letter of 01101 is 0, and the arrow labeled ‘0’ from A goes to A itself. We are now on stage A. The second letter 1 goes to B and from B, we see that the third letter 1 goes to stage C. Any letter here comes to C itself and by the time we are done with the letters, we see that we end on C. Thus, the automaton “accepts” 01101. Try seeing where 0100 goes. (Hint: The automaton rejects it).

See that the automaton described above accepts any word of binary2.0 and rejects any word that is not in binary2.0. Since binary2.0 can be described by this DFA above, we call this a regular language. See if you can come up with a DFA that only accepts words with equal number of 1’s and 0’s. This language might not be regular!

Please note that any inaccuracies are mine and mine alone. This article does not reflect on the speaker but instead can be thought of as my notes from his talk on December 10, 2024 at Krea.

Dr. Inzemamul Haque is currently a postdoctoral fellow at IIT-Kanpur. He completed his PhD. from IISc. Bangalore and interviewed to be a faculty here at Krea in the Computer Science Department.