2
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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):

Automaton recognizing $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$.

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ thanks, so if i got your hint, L1 will not contain anbn for a big enough n? still, what makes them regular? can I infer the languages are finite? $\endgroup$ – yoad w Jan 29 '16 at 8:57
  • $\begingroup$ Yes for your first question. For the second one, see Hint 2. $\endgroup$ – J.-E. Pin Jan 29 '16 at 9:13
  • $\begingroup$ I'm not quite sure i got your hint, but it gave me the following idea: split L1 into a union of small languages, each in the format : (ab)^n...(a^11b)^n, same for (ba). So that is a union of languages with a given regular expression. $\endgroup$ – yoad w Jan 29 '16 at 9:30
  • $\begingroup$ That is not enough... Consider a word like $(a(ab)^nb)^m$. $\endgroup$ – J.-E. Pin Jan 29 '16 at 9:35
  • $\begingroup$ Still, didn't get your clue. In order to not spam the discussion, I'll just sit on it for a while. Thanks anyway. $\endgroup$ – yoad w Jan 29 '16 at 9:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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