3

I would like to see some proofs to show if a particular string in machine $M$ which DFA is decidable or not. I am trying to find some results on this but those are not appropriate. Any examples or proofs would be of great help.

The scenario I am trying to prove is

If I have a language that contains $2$ words ($w_1$ and $w_2$), when I send these words to a machine $M$ which is $DFA$, then $M$ should accept/reject the language based on these conditions "$w_1$ is a substring of $w_2$, $w_1$ should not be empty and $w_1$ is not equal to $w_2$"

Deepak
  • 57
  • Should "s1 is subset of s2" be "s1 is substring of s2"? – Code-Guru Oct 06 '14 at 03:07
  • "S1 is subset of S2" – Deepak Oct 06 '14 at 03:08
  • What are S1 and S2? Are they subsets of the language $L(M)$ or strings of the language? – Code-Guru Oct 06 '14 at 03:08
  • They are strings (s1 & s2) in language L(M), where "s1 is subset of s2" – Deepak Oct 06 '14 at 03:11
  • Your question seems incomplete. A decidability problem must be stated in the form of a yes/no question. What is the question which you are trying to prove decidable? – Code-Guru Oct 06 '14 at 03:12
  • Since $s1$ and $s2$ are strings, not sets, it makes no sense to say that $s1$ is a subset of $s2$. On the other hand, it does make sense to say that $s1$ is a substring of $s2$. – Code-Guru Oct 06 '14 at 03:13
  • If I understand the question correctly, you need to show that the language $L(M)$ with the given characteristics is decidable. Is this correct? – Code-Guru Oct 06 '14 at 03:19
  • Also, since $S_1$ is a subset of $S_2$, they must both be subsets of $L(M)$, not strings. – Code-Guru Oct 06 '14 at 03:20
  • well, by rephrasing the question, If I have a language that contains 2 words (w1 and w2), When I send these words to a machine M which is dfa, then M should accept/reject the language based on these conditions "w1 is a substring of w2, w1 should not be empty and w1 is not equal to w2". Please let me know if I am clear – Deepak Oct 06 '14 at 03:27
  • That is a much clearer explanation. I think you should edit your question with that information. – Code-Guru Oct 06 '14 at 03:30
  • 1
    This doesn't sound like a question about a language. You say "I have a language that contains 2 words, $w1$ and $w2$. Are these the only words in your language? (They are the only words you mention.) A finite language is always decidable. But you are talking about a machine that determines whether certain properties hold for these two words. That question can be answered by a machine in finite time, but what does it have to do about decidability? If you mean to have a language of many strings, you need to explain what you have more clearly. – Steve Kass Oct 06 '14 at 04:27

1 Answers1

4

To show that a language is decidable, we need to create a Turing machine which will halt on any input string from the language's alphabet. Since $M$ is a dfa, we already have the Turing Machine and just need to show that the dfa halts on every input. To do this, pick a generic string, say $w$, and show that the machine $M$ will either accept or reject this string.

Code-Guru
  • 2,176
  • Any language accepted by a DFA (i.e. a regular language) is decidable. This is true since the DFA can be simulated by a Turing machine (DFA is weaker than Turing machine). – MHS Oct 07 '14 at 04:34
  • In particular every finite language is regular and thus decidable. Not sure you are saying your language only consists of $w_1$ and $w_2$, but in this case it would be decidable. – MHS Oct 07 '14 at 04:36
  • Will i be able to prove this using pumping lemma? or any other tool? – Deepak Oct 09 '14 at 18:45
  • @DeepakMudiam No, you don't need to use the pumping lemma. You already know that $L(M)$ is regular because $M$ is a DFA. – Code-Guru Oct 09 '14 at 23:37