- Thread starter
- #1

- Apr 13, 2013

- 3,723

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?

- Thread starter evinda
- Start date

- Thread starter
- #1

- Apr 13, 2013

- 3,723

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?

- Jan 30, 2012

- 2,502

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:

- Thread starter
- #3

- Apr 13, 2013

- 3,723

I understand...And could it also be shown with the Myhill-Nerode theorem?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.

- Jan 30, 2012

- 2,502

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

- Thread starter
- #5

- Apr 13, 2013

- 3,723

So,I have to find some of the infinite equivalence classes or do I have to do something else?Yes, it's actually easier than using the pumping lemma.

- Jan 30, 2012

- 2,502

- Thread starter
- #7

- Apr 13, 2013

- 3,723

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

- Jan 30, 2012

- 2,502

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.

- Thread starter
- #9

- Apr 13, 2013

- 3,723

Could you explain me further how you concluded that the language is regular? I haven't got itActually, 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^*$.

- Jan 30, 2012

- 2,502

- Thread starter
- #11

- Jan 30, 2012

- 2,502

- Thread starter
- #13

- Apr 13, 2013

- 3,723

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

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.

- Thread starter
- #14

- Apr 13, 2013

- 3,723

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?I haven't understood why the language coincides with \(\displaystyle \Sigma^{*}\) .Could you explain me why it happens?

- Jan 30, 2012

- 2,502

I already have: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^*$

- Thread starter
- #16

- Apr 13, 2013

- 3,723

Ok,thank you very much!!!!!!!!I already have: