I need to find a DFA for this language: L = { $ \omega = xy \in (a,b)^*\mid |x|_a = |y|_b $ }

  • $\begingroup$ You may want to clarify what $|x|_y$ means: is this the same as $\#_y(x)$, i.e. the count of character $y$ in the string $x$? $\endgroup$
    – wvxvw
    Sep 29, 2015 at 12:09
  • $\begingroup$ This is a trick question. The point is that DFA usually cannot compare lenghts. Here the language can be rewritten in a much simpler way. Well, see the answer. $\endgroup$ Sep 29, 2015 at 12:29
  • 1
    $\begingroup$ Hello! We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you wrote your thoughts and what you could not figure out. It will definitely draw more answers to your post. Until then, the question will be voted to be closed / downvoted. You may also want to check out our reference questions, or use the search engine of this site to find similar questions that were already answered. $\endgroup$ Sep 29, 2015 at 14:07

1 Answer 1


Let $w=w_1\dots w_n$ be any word in $\{a,b\}^*$. For $i=0,\dots,n$ consider the values $d_i(w):=|w_1\dots w_i|_a - |w_{i+1}\dots w_n|_b$. We can prove

  • $d_0(w) = - |w|_b \le 0$,
  • $d_n(w) = |w|_a \ge 0$,
  • $d_{i+1}(w) = d_i(w) + 1$ for $i=0,\dots,n-1$.

This implies that there must be some $i$ with $d_i(w) = 0$, and therefore $w\in L$. So $L=\{a,b\}^*$.


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