Solved

Posted on 2011-04-27

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).

5 Comments

Also, since regular languages are undecidable, you could just show (without any reductions) that L(M) is regular.

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.

By clicking you are agreeing to Experts Exchange's Terms of Use.

Title | # Comments | Views | Activity |
---|---|---|---|

Excel object stays open | 19 | 56 | |

countX | 22 | 50 | |

algorithm | 15 | 51 | |

countAbc challenge | 9 | 35 |

This is about my first experience with programming Arduino.

Join the community of 500,000 technology professionals and ask your questions.

Connect with top rated Experts

**22** Experts available now in Live!