I am having trouble writing a formal proof for this. I understand that we have an infinite regular language. This means that we have uncountable many subsets of the infinite regular language and due to this we have a subset which is undecidable. However, I don't know if this reasoning completes the proof or not. What's a recommended way to answer this kind of question in exam?


Yes, that sounds convincing.

Note that your argument proves something stronger than what you were asked for, though -- namely that every infinite language (regular or not) has an undecidable subset.

With the particular focus on regular languages, the intended solution might have been something like using the pumping lemma to find $x,y,z$ such that $xy^nz$ is in your language for every $n$, and then consider the subset $\{xy^nz\mid n\in A\}$, where $A$ is your favorite undecidable set of natural numbers.

  • $\begingroup$ The argument with the pumping lemma probably needs a remark for cases like $x=y=z$ or with multiples, where the numbers of the original undecidable set are not as obviously visible; or suffix/prefix combinations from x/z that generate an additional factor y. Of course, a shift of an undecidable set by a fixed number will still be undecidable. $\endgroup$ – Peter Leupold Apr 26 '18 at 8:28
  • $\begingroup$ @PeterLeupold: I'm imagining choosing and fixing $x,y,z$ first. Once their values are known (and $y$ is nonempty), then for each word there is only on $n$ such that it can be $xy^nz$. $\endgroup$ – Henning Makholm Apr 26 '18 at 10:26

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.