In: Computer Science
Prove by construction that the language An = { ai | i is a multiple of n } is regular.
In other words the language An contains all strings composed of the letter a some multiple of n times
The DFA for the language
which is equivalent to saying that "i" is a multiple of "n", works
as follows. It keeps track of the remainder of the number of 'a's
seen so far when divided by the number 'n'. Each time it sees an
'a', the remainder is increased by 1. When the remainder reaches
n-1, it is looped back to 0 on seeing another 'a'. The machine
accepts if and only if the remainder is finally 0. Note that "i" is
divisible by n if the remainder is 0.
The DFA is the following:
where the starting state is
because initially there are 0 'a's, hence the remainder is 0
initially.
The transitions are;
, these are the transitions when the remainder is increased.
. This is the transition where the remainder loops back to 0.
The DFA thus constructed accepts the given langauge, as explained above. Comment in case of any doubts.