Suppose we have language $a^{\binom{n}{k}} n,k \in N$ is this language regular ? If it is not, I should use pummping-lemma? It it is regular, I will use proof by induction ?

  • 2
    $\begingroup$ What do you think? What have you tried? $\endgroup$ – Yuval Filmus Oct 26 '15 at 19:45
  • 1
    $\begingroup$ 1. I'm not sure what your language is. Can you proof-read it and use standard notation? I suspect you are missing some symbols from the definition of the language. $\endgroup$ – D.W. Oct 26 '15 at 21:53
  • 1
    $\begingroup$ 2. What have you tried? Your question is a very basic one. Since you did not include much of an attempt to solve it on your own, we have little to work with. Let me direct you towards our reference questions which cover your problem in detail. Please work through the related questions listed there, try to solve your problem again and edit to include your attempts along with the specific problems you encountered. Is there any reason this question should not be closed as a duplicate of one of those? $\endgroup$ – D.W. Oct 26 '15 at 21:53

Hint. For any integer $n>0$, $\binom{n}{1}=n$, so can you specify what strings are in your language?

| cite | improve this answer | |
  • $\begingroup$ Okay, so, because of hint $a^{n}$ strings are like w4 = a.a.a.a (n-times concatenated language a) $\endgroup$ – POC Oct 26 '15 at 21:00
  • $\begingroup$ Yup. So your language is at least $\{a^m\mid m>0\}$ and it might be larger than that if you adopt the convention that $\binom{n}{k}=0$, as many people do. Both of there are, of course, regular. $\endgroup$ – Rick Decker Oct 27 '15 at 0:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.