formal languages - why is this regular?

Question

I'm studying for a test on formal languages and automata.

I came upon the following question (translating, so i apologize for the non-formal english):

$L_1$ is the language composed of all words over $\{0,1\}^*$ in which every prefix $u$ satisfies $-10 \leqslant |u|_a - |u|_b \leqslant 10$.

$L_2$ has similar definition, with the same boundaries over $v$, only $v$ can be any substring in $L_2$.

what can we say about $L_1 \cap L_1^R$, and $L_2$? (if someone could refer me to MathJax guide..).

I thought that Since $L_1$ also include $|u|_a - |u|_b = 0$, it includes the string $a^n b^n$, thus making it context free (at the very least).

Answers declare that both are regular. Could someone help me understand why? I know that regular languages are closed under reverse and intersection, so the main question could refer to $L_1$, $L_2$ alone.

Many thanks, yoad.

Answer 1

Hint 1. Does any prefix of $a^nb^n$ satisfies your condition?

EDIT (in answer to your comment)

Hint 2. Consider words of the form $(ab)^n$. Do they belong to $L_1$? You should first try to solve your exercise with the bounds $1$ and $-1$ instead of $10$ and $-10$.

Answer 2

Construct an automaton that recognizes $L_1$.

The idea is as follows: The automaton must keep track of the running total $|u|_a - |u|_b$ as you go along the word (i.e. $u$ is the part of the word that the automaton has read up to now). If at any point, this running total runs strictly above 10 or below -10, the word can not belong to the language anymore, since some prefix (namely the part of the word that you have read up to now) does not satisfy the requirement. Conversely, if at the end, this has not happened, then the word belongs to the language.

To do this, you should not need more than about 22 states in your automation. I leave the formalities to you.

EDIT: Here is the solution to why $L_2$ is regular. First, recall that the class of regular languages is closed under complementation, so that it suffices to show that $L_2^c$ is regular. Now, the following $\varepsilon$-NFA reconginzes $L_2^c$ (apart from the fact that I replaced the number 10 by 3 to restrict the automaton to a more manageable size):

$L_2^c$" />

Additional explanation of the idea: A word is in $L_2^c$ if there is some starting point (of the substring) such that the word beginning there has at some points at least 11 more $a$ than $b$ or vice versa. The automaton "guesses" this starting position (from the first state) and then transitions (with an $\varepsilon$-transition) to the actual body of the automaton where it verifies that there are at least 11 more $a$ than $b$ (in our case $4$ more), or $11$ more $b$ than $a$.