0
$\begingroup$

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

$\endgroup$
3
  • $\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
    Commented 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$ Commented 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$ Commented Sep 29, 2015 at 14:07

1 Answer 1

4
$\begingroup$

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\}^*$.

$\endgroup$
2
  • $\begingroup$ You have now also answered Finite strings and relationships between words part 2). A question which was closed formally because "unclear what you're asking". $\endgroup$ Commented Sep 29, 2015 at 12:28
  • $\begingroup$ And Yuval already hinted at it there, I see. $\endgroup$ Commented Sep 29, 2015 at 12:46

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