Today in my blog I’m going to discuss a question which happened to be very interesting one when I went deeper into its theories. Of course, music would make even the worst problem sweeter!
Introduction about the problem background
Thāt is a mode used in North Indian music. They are expressed using the basic music notes known as “swara”; Sa, Re, Ga, Ma, Pa, Dha, Ni. Vishnu Narayan Bhatkhande (1860-1936) is known to be the father of modern that music. Using the seven notes he identified 10 different thāts which we consider throughout this blog.
As mentioned above, there are seven basic notes in “sargam” (the seven keynotes are collectively known as “sargam”) which can be again classified in the following manner:
- All seven swaras can be natural. In fact, Sa and Pa are always natural.
- Re, Ga, Dha, Ni can be natural or flat, but never sharp.
- Ma can be natural or sharp, but never flat.
In music we denote Re, Ga, Dha, Ni being flat by underlying each note, i.e. Re, Ga, Dha, Ni. The sharp swara is denoted by Ḿa.Now we have seven basic notes with Sa and Pa always being natural and Re, Ga, Dha, Ni and Ma being in one of two forms as described earlier. When we assume that all keys should be in ascending order with Sa and Pa always being natural and other five in only one of two forms, we get altogether 32 combinations.
Bhatkhande considered only ten from those 32. They are the thāts I mentioned above.
I had to come up with a Finite Automata that can accept all 10 thāts. Before that, we have to establish a symbol convention to encode all 10 thāts so that we can feed them to the DFA as strings.
Using the above symbols, we can encode the 10 basic Thāts as follows:
- Asavari: S R g m P d n
- Bhairava: S r G m P d N
- Bhairavi: S r g m P d n
- Bilaval: S R G m P D N
- Kafi: S R g m P D n
- Kalyan: S R G M P D N
- Khammaj: S R G m P D n
- Marva: S r G M P D N
- Pooravi: S r G M P d N
- Todi: S r g M P d N
When constructing the DFA for the above scenario, we can simply follow the steps shown below:
1. Start from the beginning state. A new state will be added only if we give the input S. Hence we can draw two states with the transition from one to another for the input S.
Figure 2 – Initial state of the DFA
Note: Whenever state 1 gets any input other than S, it will go to another non-accepting state. This is because of the properties of a DFA. Since this non-accepting state does not have an impact on the final DFA, I will refer to them as dump states. For simplicity, I will not draw these dump states.The state 2 will go to two non-accepting states if it gets R or r. For all other inputs, it will go to the dump state.
2. The state 2 will go to two non-accepting states if it gets R or r. For all other inputs, it will go to the dump state.
Figure 3 – After completing 2 characters in the string
3. In this manner, we can add states for each consecutive input a state can get. This will give a kind of binary tree with each state having at least two inputs.
4. At the end of each path we add an accepting state as shown below.
The Asavari thāt can be shown as:
Figure 4 – States of the DFA accepting Asavari thāt
5. In this manner we can build the whole tree with 10 separate paths giving 10 acceptance states.
6. At the end we can merge some of these paths in such a way that, merging does not create new or additional paths. This merging is done to minimize the number of states.
7. Remember that each state has one transition that will go to the dump state for all the remaining inputs. They are not shown in the diagram in order to make it readable.
8. We can even merge the accepting states as shown in the below DFA:
9. The final DFA will be:
Figure 6 – Final DFA accepting 10 basic thāts (without showing the dump states)
Ok, that’s it! Hope you understand most of it. If you have any further improvements to suggest, feel free to drop a comment below.