HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Language where every prefix has almost equal a's and b's

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
almostequalwhereandeverylanguagehasprefix

Problem

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?

Solution

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?

Context

StackExchange Computer Science Q#19073, answer score: 4

Revisions (0)

No revisions yet.