0

If I want a language where the entries are in the form of $\gamma A^{n+2}\gamma A^{n+2}...\gamma A^{n+2}$, is it possible to write a regular expression as $(\gamma A^{n+2})^*$, or is it weird to have that '$n+2$? The languages are different for each case on $n$; for example when $n=1$, the language can be expressed by $(\gamma AAA)^*$ and when $n=3$, the language can be expressed by $(\gamma AAAAA)^*$. I don't want to write as $(\gamma AAAA^*)^*$ since I want the number of $A$s in every interval be exactly $n+2$ for each case of $n$. Thank you for the help.

MNSAR
  • 5
  • 1
    I'm just wondering whether this is math or CS. – JRC May 09 '23 at 03:25
  • I am doing pure mathematics including algebra, graph theory, etc. In this case, my study involving sequences and formal languages, which I believed it is part of CS. – MNSAR May 09 '23 at 03:49

2 Answers2

1

(Forgive me for missteps, I’m a computer scientist not a mathematician)

I think that that notation is fine, since a regex with “n” isn’t really one regex, but describes a family of them. At each n, the result is a valid regex.

minerharry
  • 21
  • 1
    As it’s currently written, your answer is unclear. Please [edit] to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center. – Community May 09 '23 at 03:49
  • I see. Thank you for the response. I really though the regex I wrote is a 'single' regex not a family of them. I always get confused because I thought that if it is a single regex, then it violated the fact that regex can be accepted by a DFA/NFA, which in my understanding, both of them cannot count and store the value of '$n$'. – MNSAR May 09 '23 at 03:58
0

I think the notation is fine as long as you make it clear that the $n$ is fixed for each language. Something like $L_n = (\gamma A^{n + 2})^*$ would be fine. And it's probably good to have an example like $n = 3$ as in the question.

You seem to be confused about how a DFA/NFA can keep track of the count $n$. It is not that finite automata cannot count, it's more that they can only count constrained by a finite memory, in terms of the states. As long as you fix $n$, you only need finite memory to count up to $n$. But if you allow $n$ to vary, the language $\bigcup_n L_n$ is not regular.

ronno
  • 11,390