3
$\begingroup$

Is the following language regular?

$$L = \{x \in \{a, b\}^* \mid \text{in every prefix \(w\) of \(x\), } 0 \le |w|_a − |w|_b \le 2\}$$

If so, give a DFA for it with as few states as possible. If you claim that it is not regular give a pumping lemma proof that it is not regular.

I'm doing exam prep and have tried pumping this to no avail. I think I created a DFA that works but I'm not entirely sure because pumping similar examples (i.e. if the number of a's is strictly greater than b's) yielded results that are not regular. Is my DFA correct? Or is there something I can pump that will fail the lemma?

DFA

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ There are more complete answers, but a general rule is that regular languages cannot count. You can do modular arithmetic, where you have a finite number of possible numbers. But think of it as a computer program. Is there some upper-bound $k$ where you never need to store a number higher than $k$ to do your computation? If not, then you need unlimited memory, and DFAs will not wori. $\endgroup$
    – Joey Eremondi
    Commented Dec 18, 2013 at 3:40
  • $\begingroup$ possible duplicate of How to prove a language is regular? $\endgroup$
    – David Richerby
    Commented Dec 18, 2013 at 8:52

4 Answers 4

Reset to default
4
$\begingroup$

Hint: as you read each letter of the input, imagine trying to keep track of the difference between the number of $a$'s and the number of $b$'s. What is the set of possible values that this could possibly take on, if the input is in $L$? What's the largest this difference could be? What's the smallest it could be?

Improve this answer
$\endgroup$
3
$\begingroup$

Since your automaton is non-deterministic, it is hard to tell whether it is doing what it is supposed to. When trying to construct an automaton in order to prove a given language to be regular, I remind myself that these machines have a very limited memory, so I try to find out what is the variable to keep in track when reading the input string, and what are its possible "states". This is the reason why this language is regular, whereas the other one you mention (number of a's is strictly greater than b's) is not : there is something small to keep in track (with constant possible states) when recognizing its strings. It is not very different from the language of strings in $\{0,1\}^*$ with an even number of 1s, or the language of strings with an equal number of '01's and '10's substrings.

Improve this answer
$\endgroup$
2
$\begingroup$

Building an automaton for a language is usually not enough to convince a professor. Worse, your comments show it is not enough to convince yourself it works.

So, your task is now to assign a meaning to each of the states: what do they represent?

I think your automaton still needs some attention besides that. For instance, it is not deterministic.

Improve this answer
$\endgroup$
2
  • $\begingroup$ "Building an automaton for a language is usually not enough to convince a professor." Say what? Being accepted by a DFA/NFA is -- literally -- the defining property of regular languages. If it genuinely is an automaton for the language, that's your proof of regularity, right there. Also, why is not being deterministic a problem? (Yes, in this case, the language isn't regular so the automaton given must accept some other language.) $\endgroup$
    – David Richerby
    Commented Feb 17, 2014 at 20:47
  • $\begingroup$ @DavidRicherby I have answered the question "Is my DFA correct?". There determinism usually matters. Aslo a little explanation of what states are meant to express is likely to be helpful to convince a professor. $\endgroup$
    – Hendrik Jan
    Commented Feb 20, 2014 at 16:46
1
$\begingroup$

This language is regular. A minimal DFA will have one state corresponding to each of the following possibilities:

  1. The prefix has $\#_a = \#_b + 0$. This is the start state for the DFA. This is an accepting state.
  2. The prefix has $\#_a = \#_b + 1$. This is an accepting state.
  3. The prefix has $\#_a = \#_b - 1$. This is an accepting state.
  4. The prefix has $\#_a = \#_b + 2$. This is an accepting state.
  5. The prefix has $\#_a = \#_b - 2$. This is an accepting state.
  6. The prefix satisfies none of the conditions given above. This is not an accepting state.

Transitions will be as follows: while in the state corresponding to $\#_a = \#_b + i$, where $-2 \le i \le 2$, transition to the state corresponding to $\#_a = \#_b + i + 1$ on seeing $a$ and the state corresponding to $\#_a = \#_b + i - 1$ on seeing $b$. If the target state is not one of the ones given in items 1-5 above, then transition instead to the dead state described in item 6; when in the dead state, all transitions are onto the dead state itself.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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