DFA examples | 3rd symbol from right in string is a | TOC.GATE.NET

DFA: 3rd symbol from right in string is a.
• DFA rejects any string of length less than 3.
• For any symbol in string, we need to consider 2 possibilities. (symbol is a, symbol is not a)
• Even if alphabet has 3 symbols, number of states is (2 power 3) NOT (3 power 3)
• Half of the total states have a as second symbol from right. So they are final states. Half of the total states Do Not have a as second symbol from right. So they are non-final states.
• To design DFA for “nth symbol from right is a”, Minimum number of states
required is (2 power n) . Half of them, (2 power n-1) will be final states and remaining half of them, (2 power n-1) will be non-final.

For Examples of minimal DFA: