• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Minimization DFA a problem with MissingTransitionException

 
ivanka ivanova
Greenhorn
Posts: 6
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello!

I already wrote all the code, but when I run it the minimization doesn´t pass the Corrector.
I made debug and I noticed that MissingTransitionException is thrown always and in the method next. I changed the method but the problem is still there. Those are the two "next" methods. The first one computes the next state after a sequence of transitions labelled from state to state. And the second one calculate true if DFA accepts the labels and the exception throws if a transitions is missing (no transition with the corresponding label exists). Any suggestions where the problem is? Thank you.




 
K. Tsang
Bartender
Posts: 3404
13
Android Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello

Have you try printing out the Iterator? More specifically the next.fromState and next.label items. Because from the look of things, your "if" statement in the 1st set of code is the key. Either this "if" never becomes true or whatever you are trying to check is wrong.

 
Winston Gutkowski
Bartender
Pie
Posts: 10273
60
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
ivanka ivanova wrote:I already wrote all the code, but when I run it the minimization doesn´t pass the Corrector.

Right, well first you need to explain what both of those terms mean.

I made debug and I noticed that MissingTransitionException is thrown always and in the method next. I changed the method but the problem is still there.

1. Which 'next' method did you change?
2. What did you change, and why did you think it would make a difference?
BTW, it's usually very bad practise to change something before you know what the problem is. And if it was simply done as a test, back it out if it doesn't work before you try anything else.

Other than what K.Tsang suggested, I can only say:
1. Your first method appears to be misnamed. From what I can see, it finds the FIRST Transition where the 'from' state and label match the ones supplied, and returns its 'to' state (which presumably is the from state of the next Transition in sequence). In fact, I wonder if your 2nd method shouldn't simply continue on from where the first one finished - in which case it might be better to have it return the Transition object, not the toState.

2. 'transitions' would appear to be a Collection of Transition objects, and so is probably an Iterable. If so, your first method could be re-written as:Note: this doesn't change its logic in any way, so it won't solve your problem; but it does make it a bit easier to read.

3. Your Transition object seems a bit involved (but maybe it's required). Personally, I'd leave out toState altogether and replace it with
Transition next;
Then "to" State becomes next.fromState. But, as I say, maybe you need it for other reasons.

4. I'm not sure what the Label is used for, and I suspect it may also be part of your problem. Independent equality checks like that can be tricky, unless you can guarantee that your Transition objects in 'transitions' are entirely consistent with the checks you're doing.

So, no answers, just questions; but maybe one of them will point you in the right direction.

Winston
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic