patternMinor
Language where every prefix has almost equal a's and b's
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?
$$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.