# Is language regular?

#### evinda

##### Well-known member
MHB Site Helper
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

##### Well-known member
MHB Math Scholar
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.

Last edited:

#### evinda

##### Well-known member
MHB Site Helper
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

##### Well-known member
MHB Math Scholar
Yes, it's actually easier than using the pumping lemma.

#### evinda

##### Well-known member
MHB Site Helper
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

##### Well-known member
MHB Math Scholar
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

##### Well-known member
MHB Site Helper
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

##### Well-known member
MHB Math Scholar
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

##### Well-known member
MHB Site Helper
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-known member
MHB Math Scholar
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-known member
MHB Site Helper
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?

#### Evgeny.Makarov

##### Well-known member
MHB Math Scholar
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

##### Well-known member
MHB Site Helper
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 $$\displaystyle \Sigma^{*}$$ .Could you explain me why it happens?

#### evinda

##### Well-known member
MHB Site Helper
I haven't understood why the language coincides with $$\displaystyle \Sigma^{*}$$ .Could you explain me why it happens?
Did you conclude that the language coincides with $$\displaystyle \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

##### Well-known member
MHB Math Scholar
I haven't understood why the language coincides with $$\displaystyle \Sigma^{*}$$ .Could you explain me why it happens?
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^*$