Welcome to our community

Be a part of something great, join today!

Is language regular?

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,718
Hello!!! :)
Could you tell me if the language {[tex]as^{(n)}ms^{(n)}t:a,m,t \epsilon \Sigma ^{*} ,s \epsilon \Sigma[/tex],[tex]m[/tex] does not contain [tex]s[/tex] and [tex]n\geq 0[/tex]} is regular?
 

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,492
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
Apr 13, 2013
3,718
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
Jan 30, 2012
2,492
Yes, it's actually easier than using the pumping lemma.
 

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,718
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? :confused:
 

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,492
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
Apr 13, 2013
3,718
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
Jan 30, 2012
2,492
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
Apr 13, 2013
3,718
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 :eek:
 

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,492
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
Apr 13, 2013
3,718
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?1387233655787.png
 

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,492
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
Apr 13, 2013
3,718
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
Apr 13, 2013
3,718
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
Jan 30, 2012
2,492
I haven't understood why the language coincides with \(\displaystyle \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

Well-known member
MHB Site Helper
Apr 13, 2013
3,718