How many strings does this automaton accept?
First of all, I wonder if this is a question on Theory of Computation, Data Structures, Graph Theory, Combinatorics, or Simple Counting!
So, how many paths to the final state exist? Here are some example strings: abcxyz, abxyzc, axyzbc. There are many ways to answer this. One simple way is to just navigate this grid in a structured way and enumerate all the strings. Since it is a small grid, you will get to 20 easily within 2 minutes! The answer is 20.
A better way is to enumerate smartly.
So, let us use our knowledge of data structures. Hierarchy is the best way to tame complexity. Also, we know that paths are best represented using trees. So, let us make a tree with nodes as valid alphabets while traversing. This way, we just need to add the leaf nodes.
We are interested in the number of strings of length 6. The number 6 is irrelevant here. Any path you take to reach the corner end state will consume a string of length 6. That’s the property of a grid. Thank God! That simplifies our life. But do you see that even if the question had abc and xyz totally messed up all over the grid in no particular order, nothing changes in your answer? It is still 20.
Add d,g,h,m,n etc. The answer is still 20!!
Now, try this. What if the grid was 100 x 100?
