Results 1 to 5 of 5
Like Tree2Thanks
  • 2 Post By tom@ballooncalculus

Math Help - Generating Finite State Automata - 5 Tuple

  1. #1
    Newbie
    Joined
    Oct 2013
    From
    London
    Posts
    3

    Generating Finite State Automata - 5 Tuple

    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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2008
    Posts
    1,034
    Thanks
    49

    Re: Generating Finite State Automata - 5 Tuple

    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
    Last edited by tom@ballooncalculus; October 16th 2013 at 06:18 AM.
    Thanks from emakarov and riow
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2013
    From
    London
    Posts
    3

    Re: Generating Finite State Automata - 5 Tuple

    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.

    Generating Finite State Automata - 5 Tuple-flow.png

    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?

    Generating Finite State Automata - 5 Tuple-question-4-fsa.jpg

    Is it possible to generate the answer as a 5-tuple without generating an flow chart?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Oct 2013
    From
    London
    Posts
    3

    Re: Generating Finite State Automata - 5 Tuple

    Now I look back on my answer it's totally wrong :-(

    I'm more confident this is correct:

    Generating Finite State Automata - 5 Tuple-flow.png
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2008
    Posts
    1,034
    Thanks
    49

    Re: Generating Finite State Automata - 5 Tuple

    Yes, correct if '1' means n or 1 to 9, and you also supply one missing label.

    Quote Originally Posted by riow View Post
    This is what the lecturer released as his answer. His is a DFSA where as yours is an NFSA?
    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

    Quote Originally Posted by riow View Post
    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.
    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?!

    Quote Originally Posted by riow View Post
    Is it possible to generate the answer as a 5-tuple without generating an flow chart?
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: September 26th 2011, 11:53 AM
  2. Finite Automata limitations
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 6th 2010, 09:57 AM
  3. Finite Automata question
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: July 7th 2009, 02:33 PM
  4. Finite Automata Question
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 25th 2008, 08:52 AM
  5. Questions relating to Sigma & Finite Automata
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: February 3rd 2008, 10:21 AM

Search Tags


/mathhelpforum @mathhelpforum