• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 414
  • Last Modified:

Undecidable Language

This is a practice problem. I have a Turing Machine M, determine if L(M) = {you, are, very, welcome}. Formulate this as a language and show that it is undecidable (hint: using reduction which is similar to Empty, Regular, and Size-2 language problems).
0
Mr_Lee
Asked:
Mr_Lee
  • 3
  • 2
1 Solution
 
TommySzalapskiCommented:
It doesn't look undecidable yet to me. Is there more to the problem definition than that?
0
 
Mr_LeeAuthor Commented:
That's all. However, I restate the hint: use a similar reduction as in the Empty, Regular, and Size-2 language problems.
0
 
TommySzalapskiCommented:
Oh, I get it. The language accepts 4 strings. I'll refine the hint. Size-2 says that a language that acceps 2 strings is undecidable. So what about 4 strings?

Also, since regular languages are undecidable, you could just show (without any reductions) that L(M) is regular.
0
 
Mr_LeeAuthor Commented:
So 4-strings will be the union of the two size-2's. And regular language is closed under union. I did not get your last statement? L(M) is regular itself. You mean I have to show it is regular?
0
 
TommySzalapskiCommented:
All I was saying was that you can choose which idea to use.
You have three good options for how to prove this.

1. You can reduce the size-2 to a size-4.

2. You can look up the proof for size-2 and modify it for size-4

3. Since regular languages are already undecidable, you could just proof that your language is regular.

You only need to do one of the above. Pick whichever is easiest and you understand the most.
0

Featured Post

Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

  • 3
  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now