I need to find a DFA for this language: L = { $ \omega = xy \in (a,b)^*\mid |x|_a = |y|_b $ }
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$– wvxvwSep 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$– Hendrik JanSep 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$– David RicherbySep 29, 2015 at 14:07
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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\}^*$.
-
$\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$ Sep 29, 2015 at 12:28
-
$\begingroup$ And Yuval already hinted at it there, I see. $\endgroup$ Sep 29, 2015 at 12:46