Digilogic

So can someone tell me a good way to determine the conditions needed to arrive in any state in a deterministic finite automata? In small ones I can usually just look at it and figure it out, but what about larger ones?

Thanks

happyraul

I'm not sure what you are asking, can you rephrase it maybe? I'm in an automata theory class so I might be able to help you, but I'm not that smart so maybe not.

Are you asking for an algorithm that given a DFA and a state of that DFA, that tells you the input(s) that get you to that state?

If that is what you are asking, then wouldn't the answer simply be to make the state you want to get to the only final state and have the resulting DFA be the machine that accepts valid inputs?

I guess I just don't know what you mean by conditions.

Digilogic

Well in my class, we use a program that allows us to draw the dfa and then type in the requirements of a string to land on that state. Then there is a feature to check it for us and tell if our conditions are right. Like if I am supposed to design a dfa that recognizes strings of a and b that end in b. The conditions of the second and final state would be that the string ends in b.

kel

Well it's pretty mechanical,
By set of conditions you must mean input string correct?
Simply follow the arrows on input character at a time till you reach the end of the input string. The state you end up is the final state.

If you want to know the conditions it takes to reach a specific state then just write the regular expression for the machine as if the final state were the specific state you want to look at.

__________________
"It better be funny"