Problem Detail: I want to show that $qquaddisplaystyle O = {M : M text{ is a DFA}, |L(M)| = 1}$. Here $|L(M)|=1$ means the DFA contains only one state. I really don’t know where to get started in this problem. Should I do something like this?
M = On input (M',w) where M' is a DFA and w is a string: - If M' accept only one member, accept. - If more than one or less than one accepted, reject.
But this will loop the program forever for the first step as it keeps testing every member after one member is selected. First step just doesn’t seem right. I think these questions might be relating to this: 1, 2
Asked By : Harshal Carpenter
Answered By : Luke Mathieson
The approach you have given is normally used for demonstrating a language is undecidable (by using the language to decided an known undecidable language). What you need to do is (implicitly or explicitly) construct an algorithm that decides the problem. As I mentioned in a comment, your notation is unclear, but both possible interpretations are decidable anyway.
- If you actually mean the property to be decided is that the language of $M$ contains one string (which is what $|L(M)|=1$ would normally mean), then you need to give an algorithm that decides whether there is exactly one, loopless path from the start state to a final state or not.
- If the property is that $M$ has only one state (normally written something like $|Q| = 1$ where $Q$ is the set of states of $M$), then you need to give an algorithm that decides whether the DFA has one state or not.
Given that (2) is essentially trivial, I assume that (1) is the actual question you’ve been asked, so you need to think of how, given, for example, a state diagram sitting in front of you, you would work out that there’s exactly one path from the start state to exactly one of the final states, that’s essentially all an algorithm really is.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/39858
