1
$\begingroup$

I am still confused over my professor's explanation on why this problem is not a DFA.

The Problem: Explain why $L = \{p^kq^k \mid k>0\}$ cannot be recognized by a DFA

My professor explained it as that it was because the DFA could not store the $k$ iterations in memory. But I still don't get it. In my mind, you just draw states $k$ number of times for $p$ and then $q$.

What's wrong with my logic?

$\endgroup$
5
$\begingroup$

The actual claim is that there is no DFA for the language $\{p^kq^k\mid k\geq 0\}$. Such an automaton would have to accept every string of the form $p^kq^k$ for any $k$, and reject every other string.

For any one fixed value of $k$, you're absolutely right that you can use $2k$ states to count off the $p$'s and the $q$'s. However, to recognize the language, the automaton would have to be able to do this for infinitely many different values of $k$, which would require infinitely many states by this method. Of course, that's not allowed in a deterministic finite automaton.

Note that this isn't a formal proof that no DFA can accept this language; rather it's just an intuition about why you should expect there to be no DFA. To formally prove the claim, you'd have to use something like the pumping lemma or Myhill–Nerode; we have a reference question about how to do that.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.