I have an idea regarding whether this language is finite or not, but for some reason I am still having some issues regarding exactly grasping what makes a language finite or infinite. I know that basically a language such as $0^*$ is obviously infinite since there can be any nonnegative number of $0$'s. However, is a language such as $(0 \cup 1)((0 \cup 1)^p)((0 \cup 1)^p)(0 \cup 1))$ also infinite? Technically, there can be any number of $0 \cup 1$ as it matters on the $p$ value, but I am also under the impression that there can only be so many values for $p$ and therefore the language is indeed finite. Can anyone explain as to why the language is either finite or infinite? I have read other examples but get a little confused when the language is in the gray area. Thanks!

  • 1
    $\begingroup$ Hello and welcome to Computer Science. The lack of helpful formatting makes your post hard to comprehend. Please take some time to improve the presentation (add some space and split to paragraphs; use Latex if possible for mathematical expressions); we collected some advice here. Thank you! $\endgroup$ – Ran G. Apr 28 '16 at 0:38
  • $\begingroup$ Sorry about that, I'm basically just looking at a Pushdown Automata and roughly translating it into a regular expression. Given the PDA, I am under the assumption that p has to be greater than or equal to 0, but that is the only condition I have. Therefore, is it safe to say that the language is infinite? Even though both the second and third term require the same value for p? $\endgroup$ – user50283 Apr 28 '16 at 0:39
  • $\begingroup$ It looks like you might have inadvertently created two accounts. I recommend you merge your accounts; please see cs.stackexchange.com/help/merging-accounts for details. Also, I suggest you create an account and register it, to ensure you retain access: see cs.stackexchange.com/help/why-register. $\endgroup$ – D.W. Apr 28 '16 at 3:56
  • $\begingroup$ I don't see the relation to PDAs. Please clarify your question. $\endgroup$ – Ran G. Apr 28 '16 at 13:08

(0 U 1)((0 U 1)^p)((0 U 1)^p)(0U1)) is not a language, but a regular expression. Moreover, to be well-defined, you must specify what $p$ is.

Is $p$ a specific value? Then, this expression generates a finite number of words -> it generates a finite language.

But maybe you look at the language generated by the above expression for any p? then, there will be infinitely many generated words.

you need to tell us what is $p$ and what is the language under consideration.


what makes a language finite or infinite

That's pretty clear by definition. In general, it's (algorithmically) impossible to tell from some description. There are also examples that are deliberately obscure so students have to think.

as it matters on the p value

Exactly. Regular expressions do, syntactically, not allow for integer variables. So you have to consider a fixed (if arbitrary) value for p.

when the language is in the gray area

There is no gray area; the question you ask is ill-posed is all. What is the exact definition of the language?


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.