Using a Deterministic Finite Automata to recognize Thāt music scales

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.

1

2Figure 1 – The 10 thāts [resources: Wikipedia]

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.

Problem description

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.

Natural Flat Sharp
Note Symbol Note Symbol Note Symbol
Sa S
Re R Re r
Ga G Ga g
Ma m   Ḿa M
Pa P  
Dha D Dha d
Ni N Ni n

Using the above symbols, we can encode the 10 basic Thāts as follows:

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.
3

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.

4

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:

7

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:

6

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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s