4
$\begingroup$

I try to show that this language is regular:

$L = $ { w $\in \ (a,b) ^ * $| for every u substring of w, $-5\le|u|_a−|u|_b\le5\}$

If I build a NFA and run on it every substring of w (skip other letters every time) - and only if they are all accepted (follows the condition) then accept w. Is it possible in NFA? Is there other way to show the regularity of the language?

Improve this question
$\endgroup$
  • 3
    $\begingroup$ You can look at the residual sets: for each $w$, let $R(w) = \{u| wu \in L\}$. For $L$ to be regular, the number of such sets ($R(w)$ for all $w$) must be finite. You can show that it's the case by noting that the only thing that matters for $R(w)$ is $\min$ and $\max$ of $ #(a) - #(b) $ for all suffixes of $w$, and they can only be between $-5$ and $5$. $\endgroup$ – Dmitry Aug 21 '20 at 21:08
  • $\begingroup$ @Dmitry I started writing that down as the answer before I saw your comment. $\endgroup$ – gnasher729 Aug 22 '20 at 16:07
7
+50
$\begingroup$

Nice question! This is a very nontrivial problem involving regular languages.

First of all: no, you cannot run an automaton on every substring of a string skipping other letters, you are supposed to run the automaton only once on the target string.

In this case it is simpler to reason on the complementary of the given language, namely on

$$L^C = \{ w \in (a,b) ^ * \mid \text{ there is a substring } u \text{ of } w \text{ such that } |u|_a−|u|_b>5 \text{ or } |u|_a−|u|_b<-5\}$$

The language $L^C$ is regular, as it is recognized by the following NFA:

enter image description here

(each state name is the difference $|u|_a−|u|_b$, the first letter of the substring $u$ is "found" nondeterministically by the NFA).

So, as $L^C$ is regular, also $L=(L^C)^C$ is.

Following Hendrick's suggestion, I tried to determinize the NFA and to draw its complement, and I get this nice DFA that recognize $L$:

enter image description here

Each name of an accepting state name is an interval: when, running the automaton, we are in state $[x_1,x_2]$ and we have read the string $z$ this means that for all $x\in [x_1,x_2]$ there is a suffix $u$ of $z$ such that $|u|_a−|u|_b=x$. Otherwise said, following Dmitry's suggestion, the automaton calculate the residual set of $z$.

In a sense, as Hendrick says, it is like we are running the automaton on each substring, but this do not mean that we can directly use a DFA that recognize strings such that the difference between the $a$s and the $b$s is in $[-5,5]$ (which would be easy to realize) and run this automaton on each substring of a given one, and in this way prove that the language is regular.

Lastly, I would write a trivial generalization of the result (I think that this is folklore, but I couldn't find a reference).

Let $T$ be a regular language on an alphabet $\Sigma$ and let $L$ be the language defined as follows:

$$L= \{ w \in \Sigma^* \mid \text{ for every substring } u \text{ of } w,\ u\in T\}$$

then also $L$ is regular.

Indeed, as above, consider $L^C$, the complement of $L$, namely

$$L^C = \{ w \in \Sigma^* \mid \text{ there is a substring } u \text{ of } w \text{ such that } u\not\in T\}$$

Then $L^C=\Sigma^*T^C\Sigma^*$, and therefore $L=(\Sigma^*T^C\Sigma^*)^C$ is regular, as the family of regular languages is closed under concatenation and complementation.

Cleary the result is still true for every family of languages closed under concatenation and complementation, but this is not a necessary condition. Indeed, the family of finite languages it is not closed under complementation, but clearly if $T$ is finite, then also $L$ is (as it is always the case that $L\subseteq T$). On the other hand, this is not true for all classes of languages. Consider the family NR of non-regular languages, then $T=\{1^p\mid p\text{ is prime}\}\in\ $NR, but in this case we have $L=\varnothing$, which is regular.

Improve this answer
$\endgroup$
  • 1
    $\begingroup$ I like your solution using the complement! But contrary to what you suggest, it is possible to run the automaton on each substring, spawning after each letter a new computation. The point here is that there are only finitely many states, so if any of the parallel computations reach the same state they can be fused, so there will always be a bounded number of runs in parallel. $\endgroup$ – Hendrik Jan Aug 22 '20 at 14:58
  • 1
    $\begingroup$ Also it is very funny (I mean instructive) to see what happens if you actually determinise the NFA from your solution. The DFA states will always contain sets of states that form an interval. The letters move the interval up and down, but the interval will never loose $0$. $\endgroup$ – Hendrik Jan Aug 22 '20 at 15:02
  • 1
    $\begingroup$ Comment to self: I now realize that adding state zero every step of the computation (when making the NFA deterministic because of the loop at state zero) is actually the same as starting a computation in parallel for every next letter of the input. So my comments kind-of match. $\endgroup$ – Hendrik Jan Aug 22 '20 at 15:52
  • $\begingroup$ @HendrikJan, thanks for noticing the error, clearly you are right, as the automaton was not deterministic! $\endgroup$ – user6530 Aug 23 '20 at 9:17
  • 1
    $\begingroup$ @tas1 You are right, but in this case we started with a nondet automaton and we explicitly were trying to make a deterministic one. That last DFA had some extra edges that are now removed. $\endgroup$ – Hendrik Jan Aug 25 '20 at 15:04

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.