Here's the flow chart:
Can you complete the labelling? (Where n is any numeral 1 to 9.)
Finite-state machine - Wikipedia, the free encyclopedia
Hi I'm am having problems figuring out the logics behind finding the states in this question. If someone could explain how they got each state in this question I would be very grateful, and would help me get my head around the logic of generating this Finite State Automata.
Question:
Define an FSA (as a 5-tuple) that recognises the language of Decimal Fractions, which includes the decimal integers and all those strings in which the 'decimal point' symbol (".") is preceded by a decimal integer and followed by any non-empty string of decimal digits that does not end with 0. For example, 0, 12, 12.0, 43.001 are in the language, but 00, 01, 12., .01, 23.010 are not.
Thanks in advance!
Here's the flow chart:
Can you complete the labelling? (Where n is any numeral 1 to 9.)
Finite-state machine - Wikipedia, the free encyclopedia
Thanks, this really helped. Here is what I got. I see how you came about it by using the transitions: n(1..9), 0 and "." . I think that was where I was having a mental block.
I think the lecturer who gave this question made an error where he wrote; "For example, 0, 12, 12.0, 43.001 are in the language". This threw me off a lot then when i say his answer I realised he made a mistake.
This is what the lecturer released as his answer. His is a DFSA where as yours is an NFSA?
Is it possible to generate the answer as a 5-tuple without generating an flow chart?
Yes, correct if '1' means n or 1 to 9, and you also supply one missing label.
No, but he merges some of the n and 0 transitions. Apart from that the two are equivalent, EXCEPT mine contains a redundant stage, my stage 5. (Move 6 into its place.) I THINK I put it there in order to accept 12.0
Well, his chart treats it as a mistake, or at any rate it rejects 12.0
But mine also fails to accept it. If you did want to accept it (even though I agree that it does rather contradict the preceding verbal definition; maybe that's why I didn't follow through) you could make my stage 5 an accepting state and then insert another stage between my 5 and 6. Try it?!
Why do without the chart? You can always convert it to a transition matrix (see wikipedia) though I doubt that's preferable as a presentation of the transition function. But I wouldn't know, I'm just going from the wiki page.