My problem exercise: L ={s $\epsilon$ {a,b}*| $\forall$ prefix $w$ of $s$ it is true that $| |w|_a -|w|_b | \leq$2 } , prove that L is regular. $|w|_a$ indicates the number of 'a's in the prefix, $|w|_b$ - number of 'b's
I've been using Pumping Lemma to prove that a language is not regular, regular expressions/Brzozowski's algorithm to prove a language is regular, but I stumbled on a few problems in the form of the title's and I have no idea where to start from. I assume I need to design some regular expression, but I don't have the intuition for it, on the other hand, where would I even start with Brzozowski?
One thing I think might work is to consider that {a,b}* is regular and the language of all prefixes of a regular language= P is also regular, so I could write P = L ⋃ $L^c$, and since P is regular, than L and $L^c$ must also be regular?
Is there a specific approach to languages that are tightly dependant on prefixes and suffixes, or is it a standard exercise like any other?
Let $S_i$, $i = \overline{-2..2}$ be state corresponding to words in $L$ s.t. $|w|_a - |w|_b = i$ and $T$ be state corresponding to words not in $L$.
Than transitions are simple: $S_i \xrightarrow{a} S_{i + 1}$ if $i < 2$, $S_i \xrightarrow{b} S_{i - 1}$ if $i > -2$, and $S_{-2}\xrightarrow{2} T$, $S_2 \xrightarrow{b} T$. Say that $S_i$ are accepting states, $S_0$ is start state and you get DFA that recognizes $L$.
In general, to create DFA, you want to split words in finite numbers of sets (corresponding to states of DFA) such that if you know which set does current prefix belong to, and what is the next letter, you can determine which set does the next prefix belongs to.