#header-inner {background-position: right !important; width: 100% !important;}

4/2/14

Finite State Automatons and Regular Expression Basics.

There's connection between finite state automatons and regular expressions.

Finite State Automatons accept input, if it matches a Pattern defined by a Regular Expression. Otherwise they process input and do not enter 'accepting' state.

That's how we can find patterns in an input - by creating Finite State Automaton to work through input, and check if it enters accepting state.

 photo fsa_zpse9ad8e28.jpg

Finite State Automaton, often named Finite State Machine (FSM).



Source: [7].

9 comments:

  1. i used word 'collection' in a free-form way, not exactly as in Java's Collection class.

    More like a 'bit sequence' to be precise, ordered, with each bit meaning something.

    ReplyDelete
  2. Finite State Machines and Regular Expressions are part of 'Languages & Automatons' Theory that investigates Computational Models & Languages related to such. There are Finite State Machines, Stack Machines, Turing Machines, Regular Expressions, Context-Free Languages with Context-Free Grammars and Contextual Languages with Contextual Grammars.

    ReplyDelete
  3. (EN) Finite State Automatons and Regular Expression Basics = (PL) Podstawy Automatów Skończenie Stanowych i Wyrażeń Regularnych.

    ReplyDelete
  4. there are other finite state automatons as well, with different amount of states, with different state names, with different transitions: either in one direction or in both directions ... bidirectional transitions are usually two arrows however ... state might be reachable or not, there can be more than one accepting state as well. there's always initial state there however.

    there's much more to 'finite state automaton theory' than that however, still ... i think so, at least ... for example: how to transform two finite state automatons into one, probably more ...

    ReplyDelete
  5. different transitions might join different states as we want, there can be both unidirectional transitions as well as bidirectional transitions, not all of them of the same type, where type is either: 'unidirectional' or 'bidirectional' ...

    not only accepting state might be reachable or not.

    'reachable' means: 'joined with rest of automaton with arrow(s), properly' ... so it can be 'reached' from 'initial state' by following 'transition arrow(s) in proper direction(s)' ...

    multiple 'accepting states' might imply that automaton returns a 'result value', as functions can.

    this is more or less classic approach to 'Finite State Automatons', i think ...

    i think people can be creative with extending theories as well, if needed or neccessary ...

    ReplyDelete
  6. see also, if You wish:

    'ARM Quant'.
    http://dragonfly-algorithm.blogspot.com/2015/04/arm-quant.html

    ReplyDelete
  7. can there be more than one initial state?
    no, according to my understanding, at least, ...

    but from 'initial state', automaton can 'transition' into one of 'other states' that we were considering as possible 'initial states' before this information was revealed, perhaps ...

    that way we can achieve similar result, i think ...

    ---
    of course there can be alternative theories as well.

    ReplyDelete
  8. see also, if You wish ... comment is important as well, probably even more than the main post, from this post's perspective, at least.

    http://dragonfly-algorithm.blogspot.com/2015/05/request-response-state.html

    ReplyDelete
  9. perhaps should work on a simple modelling notation for finite state automatons in context of 'class diagram' model ... basicly class inheritance hierarchy with properties (state) listed, as on the image above.

    with 'distinct states on higher or lower abstraction level' included in notation. higher abstraction level basicly joins few of states from lower abstraction level, then 'encapsulates' ('hides') them all in one state.

    we can have for example: more abstract state of 'shooting' that on less abstract level might be automaton with 3 states 'shooting accurately', 'shooting quickly', 'shooting to guide enemy somewhere', etc ...

    with transitions & transition causes presented as well - more or less abstractly.

    ReplyDelete