For each , let be , where are different from each other. For a word , we write for the number of occurrences of in . We define the languages and over by:
and
Answer the following questions.
(1) Give a deterministic finite state automaton with states that accepts .
(2) Give a non-deterministic finite state automaton with states (without -transitions) that accepts .
(3) Prove that, for every , every deterministic finite state automaton that accepts has at least states.
(4) Prove that, for every , every non-deterministic finite state automaton (without -transitions) that accepts has at least states.
Begin with an -NFA as depiced in Fig. (2-a).
It "guesses" which letter appears even number of times.
To make it -free, we either follow him: https://youtu.be/sq-dLKAd6bo?t=1714 or consider the followig:
starting from start state, how far, i.e. which states can we reach on letter ?
There are such states.
We simply draw an edge to those states.
Do the same for .
The final answer is on Fig. (2-b)
Prove that, for every , every deterministic finite state automaton that accepts has at least states.
First, I'll show that there is a DFA with states.
We can encode states of DFA as a binary string of length , where iff numbers of 's is odd in so-far read sequence, else .
A state is accepting if its binary representation has at least one zero.
There are such strings.
Now, I'll show that there is no DFA with less than states.
If the DFA had fewer than states, then there would be some state such that the DFA can be in state after reading two different sequences of length , say and .
If the sequences were of different parity, i.e. one of the sequences had a letter which appears even number of times, and the other sequence hadn't, then would be both accepting and nonaccepting state.
If the sequences were of the same parity, then we could append some sequence to and such that and have different parity.
Consider state that the DFA enters after reading .
Then must be both accepting and nonaccepting, since either of
and is accepted and the other isn't.
This problem could be also one-lined using Myhill-Nerode theorem.
The only one difficulty here is to define equivalent classes.
Try fiddling with binary strings.
Prove that, for every , every non-deterministic finite state automaton (without -transitions) that accepts has at least states.
Begin with constructing DFA accepting the same way as in Q3 – except that has only one accepting state, a string of all 's.
Obviously this DFA is also a~NFA.
The equivalent NFA simply cannot guess parity of some letters: it has to remember information of parity of each letter.
As shown in Q3, every letter requires bits, so minimum of states are required.
