Regularity of a Language without the Letter S Repeated n Times

[evinda]

Hello! :)
Could you tell me if the language {$$as^{(n)}ms^{(n)}t:a,m,t \epsilon \Sigma ^{*} ,s \epsilon \Sigma$$,$$m$$ does not contain $$s$$ and $$n\geq 0$$} is regular?

 

[Evgeny.Makarov]

A finite automaton, like a preschooler, can count only up to 100, give or take. Therefore, counting the number of $s$ characters in the first substring and comparing it with the number of $s$ characters in the second substring is beyond it. When $n$ becomes large, the automaton starts forgetting exactly how many $s$ characters it read: "Was it 123? Or 223? Or 523? Darn, I forgot!". So this language is not regular.

 

[evinda]

A finite automaton, like a preschooler, can count only up to 100, give or take. Therefore, counting the number of $s$ characters in the first substring and comparing it with the number of $s$ characters in the second substring is beyond it. When $n$ becomes large, the automaton starts forgetting exactly how many $s$ characters it read: "Was is 123? Or 223? Or 523? Darn, I forgot!". So this language is not regular.

I understand...And could it also be shown with the Myhill-Nerode theorem?

 

[Evgeny.Makarov]

Yes, it's actually easier than using the pumping lemma.

 

[evinda]

Yes, it's actually easier than using the pumping lemma.

So,I have to find some of the infinite equivalence classes or do I have to do something else?

 

[Evgeny.Makarov]

Not infinite equivalence classes, but infinitely many equivalence classes. In other words, infinitely many words that are not equivalent. And this in turn means that for every pair $u,v$ of such words there exist a word $w$ such that $uw$ is in the language, but $vw$ isn't ($u$, $v$ and $w$ by themselves are not necessarily in the language).

 

[evinda]

Not infinite equivalence classes, but infinitely many equivalence classes. In other words, infinitely many words that are not equivalent. And this in turn means that for every pair $u,v$ of such words there exist a word $w$ such that $uw$ is in the language, but $vw$ isn't ($u$, $v$ and $w$ by themselves are not necessarily in the language).

Could you give me an example of a pair $u,v$ of such words,so that I can try to find some else?

 

[Evgeny.Makarov]

Actually, when I think about it again, it seems that this language coincides with $\Sigma^*$ and, therefore, is regular. Indeed, let $n=0$ and $m=t=\varepsilon$. Then $L\ni as^nms^nt=a$, and since $a$ is arbitrary, such words cover the whole $\Sigma^*$.

If the above reasoning is right, then this is either a trolling exercise intended to teach students to think twice or a poorly designed problem. Poor notation choice—$n$ ranges over natural numbers while $m$ ranges over strings—does not help, either.

To understand the idea behind using Myhill-Nerode theorem, consider the language $\{0^n10^n\mid n\ge0\}$. The words $0^n1$ for various $n$ are non-equivalent.

 

[evinda]

Actually, when I think about it again, it seems that this language coincides with $\Sigma^*$ and, therefore, is regular. Indeed, let $n=0$ and $m=t=\varepsilon$. Then $L\ni as^nms^nt=a$, and since $a$ is arbitrary, such words cover the whole $\Sigma^*$.

Could you explain me further how you concluded that the language is regular? I haven't got it

 

[Evgeny.Makarov]

Well, I gave a pretty detailed explanation why $L=\Sigma^*$. If you have questions about that, then say what is not clear. Or are you asking why $\Sigma^*$ is regular? Can you write an automaton that accepts $\Sigma^*$?

 

[evinda]

Well, I gave a pretty detailed explanation why $L=\Sigma^*$. If you have questions about that, then say what is not clear. Or are you asking why $\Sigma^*$ is regular? Can you write an automaton that accepts $\Sigma^*$?

Is it maybe like that?View attachment 1782

 

[Evgeny.Makarov]

That's correct. In general, finite languages (including the empty one: no accepting states) are regular, and the class of regular languages is closed under complements. Thus, if a language has a finite number of words (including 0) or if a language is $\Sigma^*$ without a finite number of words (in particular, $\Sigma^*$ itself), then it is regular.

 

[evinda]

Actually, when I think about it again, it seems that this language coincides with $\Sigma^*$ and, therefore, is regular. Indeed, let $n=0$ and $m=t=\varepsilon$. Then $L\ni as^nms^nt=a$, and since $a$ is arbitrary, such words cover the whole $\Sigma^*$.

If the above reasoning is right, then this is either a trolling exercise intended to teach students to think twice or a poorly designed problem. Poor notation choice—$n$ ranges over natural numbers while $m$ ranges over strings—does not help, either.

To understand the idea behind using Myhill-Nerode theorem, consider the language $\{0^n10^n\mid n\ge0\}$. The words $0^n1$ for various $n$ are non-equivalent.

I haven't understood why the language coincides with $$\Sigma^{*}$$ .Could you explain me why it happens?

 

[evinda]

I haven't understood why the language coincides with $$\Sigma^{*}$$ .Could you explain me why it happens?

Did you conclude that the language coincides with $$\Sigma^{*}$$,because of the fact that all languages are equivalent?If so,does this mean that all languages are equivalent with the empty set?

 

[Evgeny.Makarov]

I haven't understood why the language coincides with $$\Sigma^{*}$$ .Could you explain me why it happens?

I already have:

Actually, when I think about it again, it seems that this language coincides with $\Sigma^*$ and, therefore, is regular. Indeed, let $n=0$ and $m=t=\varepsilon$. Then $L\ni as^nms^nt=a$, and since $a$ is arbitrary, such words cover the whole $\Sigma^*$

 

[evinda]

I already have:

Ok,thank you very much!