1
$\begingroup$

As you can see from the title this is the impression that i have on this problem, but probably it isn't impossible.

The required DFA is :

"The set of the strings with equal number of 0 and 1 such that for each prefix the difference between the number of 0's and the number of 1's is minor(<) than 2".

Maybe I've misread the requirements I've thought of them as follows :

  • by prefix I thought of all the strings with length < than the original one, for example in my opinion the prefixes for "cat" are "c" and "ca" but not "cat";

    • "the difference between the number of 0's and the number of 1's is minor(<) than 2" by this i thought that we should have (number of 0 - number of 1) < 2, but now I'm realazing that even (number of 1 - number of 0) < 2 should be fine.

One user suggested to do this :

"Note that you can build a simple DFA which checks if the difference between the number of ones and the number of zeroes never exeeds 2 for any prefix of the input string: Add accepting states qk for −2≤k≤2 (where q0 is the initial state) and a rejecting sink state qs with transitions qk→qk+1 via 1 and qk→qk−1 via 0 for appropriate values of k and qk→qs for the other values."

but I don't understand quite well what it means, I've tried some solutions on my own and they don't work properly :

enter image description here

Any possible solutions? EDIT The DFA should be impossible as a matter of fact : here is the explanation

$\endgroup$
  • $\begingroup$ Where are you stuck at the smaller problem? You should be able to simply "do it" -- draw the states with the meaning proposed and then think about where the outgoing transitions from every state should go. $\endgroup$ – DCTLib Jun 2 '18 at 11:23
  • $\begingroup$ @DCTLib I've read this article and it seems that it is impossible to draw an automata of equal number of 0's and 1's quora.com/… so the dfa that i'm required to do is also impossible. however i don't understand the suggestion that I talked about in my question so i'm not understanding how to do the automata for the difference of 0's and 1's, i'll edit the questions with the dfa that i've tested for thesmaller problem $\endgroup$ – Zeno Raiser Jun 2 '18 at 12:16
  • $\begingroup$ Note that the answer on quora is a for a different question -- the requirement that the difference between the numbers of 0s and 1s for every prefix word needs to be at most 2 is missing -- with this restriction, it is possible to build a DFA. $\endgroup$ – DCTLib Jun 2 '18 at 14:15
  • $\begingroup$ Yes but it must also have equal number of 0's and 1's which can't builded, it's not a restriction but an expansion of the requirement. If it possible to build could you post it? Thanks $\endgroup$ – Zeno Raiser Jun 2 '18 at 14:50
  • $\begingroup$ Zeno Raiser, that would mean that I do your homework. Note that in your argument "but it must also have equal number of 0's and 1's" you assume that the intersection of a regular and a non-regular language is necessarily non-regular. This is not the case -- See cs.stackexchange.com/questions/49448/… for details. $\endgroup$ – DCTLib Jun 2 '18 at 15:06
2
$\begingroup$

Note: I am the user who gave the comment cited in the OP on the CSTheory thread. Also, I am writing this as an answer rather than a comment to JohEker's post as I do not have enough reputation here to comment.


The idea is to exploit that we have a finite, local bound on the difference between zeroes and ones in the input word, i.e. we accept every word where this difference does not exceed 1 at any point. Note that if we drop the requirement that this holds for all prefixes, then the language is not regular (and thus not recognized by a DFA) by the Myhill-Nerode theorem as pointed out by JohEker.

So let $\#0(w)$ and $\#1(w)$ denote the number of ones and zeroes in the word $w$ respectively. To build a DFA from the idea above, we see that a word $w$ should be accepted if every prefix $v$ of $w$ satisfies $|\#1(v) - \#0(v)| \leq 1$, or equivalently $-1 \leq \#1(v) - \#0(v) \leq 1$. We can keep track of the value $\#1(v) - \#0(v)$ by creating a state for every value of it that we care about and specifying transitions between these states to model how the counter changes when we read a $0$ or a $1$. Combining this with our previous idea that we only need to know if the value of the counter is between $-1$ and $1$, we create three states $q_{-1}, q_0$ and $q_1$.

Clearly we want the initial value of the counter to be $0$, so we use $q_0$ as the initial state of our automaton and we transition from $q_k$ to $q_{k+1}$ if we read a $1$ (for $k \in \{-1, 0\}$ -- else we leave the space of values that we are interested in; more on this later) and similarly we transition from $q_k$ to $q_{k-1}$ (for $k \in \{0, 1\}$). As we want to accept the words for which the counter ends up at 0, we also define $q_0$ as the only accepting state.

Now, what happens if the counter does not stay within $\{-1, 0, 1\}$? We want to reject the input.

In our automaton, this corresponds either to reading a $0$ while we are in the state $q_{-1}$ (i.e. we have $\#1(v) - \#0(v) = -1$ that for the input $v$ before reading the $0$ and thus $\#1(v0) - \#0(v0) = -2$) or reading a $1$ while we are in the state $q_1$. So we introduce a new, "rejecting" state $q_s$ (also called a sink-state as the DFA cannot escape from this state once it is reached) which we transition to in case we detect one of the above-described scenarios. This now completes the description of our DFA, which looks like this:

enter image description here

$\endgroup$
  • $\begingroup$ the dfa shouldn't accepts string such as "0" or "1" since the number of 0's and 1's is different but this accepts them $\endgroup$ – Zeno Raiser Jun 2 '18 at 23:23
  • $\begingroup$ Oops, sorry, I misread that part. I have edited my answer to address this problem. $\endgroup$ – Watercrystal Jun 2 '18 at 23:32
0
$\begingroup$

How does the formal description of this language look like? A finite DFA does not support infinite languages that require to balance the different parts together, because we would have to keep building new states forever. Lets say we have L = {0^i 1^j | i = j}. Which is, we need to start making 0s, and then we need to make equal amount of 1s. This would be easy for the strings {"01", "0011" "000111"}. By just manually add that path of states to the DFA. But what happends with this string s = "00000000001111111111". We would have to make a path allowing exactly ten 0s, followed by ten 1s, and we would have to add another path for the next string, we would eventually run out of memory.

Using the pumping lemma for regular languages, we can also see that languages such as this are not regular, and if it is not regular, it simply cannot be converted to a DFA.

EDIT: Reading the question again i realised the language does not force us to give the stringbuilds in specific order, therefore by always controlling | #0(w) - #1(w) | < 2 and then accepting when the difference is 0, we can do something like this.

DFA accepting structurally smaller strings with a difference strictly smaller than 2

$\endgroup$
  • $\begingroup$ the description of this language is literally the one that i wrote, translated from italian, i haven't a formal description they didn't gave us in uni. $\endgroup$ – Zeno Raiser Jun 2 '18 at 13:39
  • $\begingroup$ This answer is a for a different question -- the requirement that the difference between the numbers of 0s and 1s for every prefix word needs to be at most 2 is missing -- with this restriction, it is possible to build a DFA. $\endgroup$ – DCTLib Jun 2 '18 at 14:16
  • $\begingroup$ Now i am confused, the question says < 2. Do we want to accept differences <= 2?, in that case my latest edit is not correct. $\endgroup$ – JohEker Jun 2 '18 at 14:22
  • $\begingroup$ @ZenoRaiser So was this the answer you were looking for or not? $\endgroup$ – JohEker Jun 2 '18 at 16:37
  • $\begingroup$ @JohEker no, for instance the string 11001100 is not accepted in your dfa but the requirements considers it as acceptable. anyway you gave me an interesting hint i'll try to think about it later $\endgroup$ – Zeno Raiser Jun 2 '18 at 16:51

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.