Solved

# Undecidable Language

Posted on 2011-04-27
403 Views
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
Question by:Mr_Lee

LVL 37

Expert Comment

It doesn't look undecidable yet to me. Is there more to the problem definition than that?
0

Author Comment

That's all. However, I restate the hint: use a similar reduction as in the Empty, Regular, and Size-2 language problems.
0

LVL 37

Expert Comment

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

Author Comment

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

LVL 37

Accepted Solution

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

### Suggested Solutions

Excel object stays open 19 56
countX 22 50
algorithm 15 51
countAbc challenge 9 35
Introduction Many of the most common information processing tasks require sorting data sets.  For example, you may want to find the largest or smallest value in a collection.  Or you may want to order the data set in numeric or alphabetical order. …
This is about my first experience with programming Arduino.
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …
In this seventh video of the Xpdf series, we discuss and demonstrate the PDFfonts utility, which lists all the fonts used in a PDF file. It does this via a command line interface, making it suitable for use in programs, scripts, batch files — any pl…