Finite State Machines in Computing
Finite States: Base
Elements in a Computing
Orchestra
Ronald Finkbine, Ph.D.
Department of Computer Science
Indiana University Southeast
rfinkbin@ius.edu
Introduction
Software Complexity
Programmer Understandability
Maintainability
Reduce by tools
Reduce by techniques
Definitions
Finite State Machine, any program
DFA, 4 tuple
1.
States
2.
Transitions
3.
Start state
4.
Accept states
Moore Machine
Mealy Machine
Elementary DFA
Accepts L={a*b+}
Incomplete
Benefits of DFAs
High-reliability
Proof or show?
Mathematics is a modeling method
Proofs are social constructs
Diagrammetics
Simple FSM Specification
Pictures are good
Graphviz.org
dot -v -Tjpeg -o beginner.jpg beginner.dot
Text file output
Show or proof?
Java code
produced
Fox Chicken Grain Problem
A man is crossing a river on the way to
market with a chicken, a bag of grain and
a fox. If left unattended the fox will eat
the chicken, and the chicken will eat the
grain. The boat will only hold the man and
one of these at a time. Your task is to
work out a sequence of crossings that will
affect a safe transfer of the man, the fox,
the chicken and the grain safely across
the river.
DFA
Text:
CeFCGeC
Translating into English, the input string
represents:
Man and chicken cross river
Man returns with empty boat
Man and fox cross river
Man returns with chicken
Man and grain cross river
Man returns with empty boat
Main and chicken cross river
Connecting FSMs into a flow
Benefits
FSMs are complete programs
Lead to parallelism
Not restricted to single language
Not sharing spaces, better security
Limits programming options, reduces
programming complexity, GOOD
Data in single layer, in surface pipe
Sample
cls
initdb.py
p0.py <input\fred.f >f1.txt
type f1.txt | indb.py NodeToken >f2.txt
type f2.txt | s3 ars.db
call s3 ars.db "select * from NodeTokens"
call s3 ars.db "select count(*) from
NodeTokens"
type f1.txt | only.py NodeToken >f3.txt
outdb.py -n ars.db NodeTokens | parse.py
numdb.py ars.db NodeTokens
FSMs can be everywhere
Software Complexity
Programmer Understandability
Maintainability
Reduce by tools
Reduce by techniques
Discover the world of Finite State Machines (FSMs) in computing through images and explanations. Learn about base elements, software complexity, DFA terminology, high reliability proofs, and practical examples like the Fox Chicken Grain Problem. Dive into FSM specifications and explore Java code generation. Uncover the art of translating input strings for DFA applications.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Finite States: Base Elements in a Computing Orchestra Ronald Finkbine, Ph.D. Department of Computer Science Indiana University Southeast rfinkbin@ius.edu
Software Complexity Programmer Understandability Maintainability Reduce by tools Reduce by techniques Introduction
Finite State Machine, any program DFA, 4 tuple 1. States 2. Transitions 3. Start state 4. Accept states Moore Machine Mealy Machine Definitions
Accepts L={a*b+} Incomplete Elementary DFA
High-reliability Proof or show? Mathematics is a modeling method Proofs are social constructs Diagrammetics Benefits of DFAs
Graphviz.org dot -v -Tjpeg -o beginner.jpg beginner.dot Pictures are good
Java code produced
A man is crossing a river on the way to market with a chicken, a bag of grain and a fox. If left unattended the fox will eat the chicken, and the chicken will eat the grain. The boat will only hold the man and one of these at a time. Your task is to work out a sequence of crossings that will affect a safe transfer of the man, the fox, the chicken and the grain safely across the river. Fox Chicken Grain Problem
Translating into English, the input string represents: Man and chicken cross river Man returns with empty boat Man and fox cross river Man returns with chicken Man and grain cross river Man returns with empty boat Main and chicken cross river Text: CeFCGeC
FSMs are complete programs Lead to parallelism Not restricted to single language Not sharing spaces, better security Limits programming options, reduces programming complexity, GOOD Data in single layer, in surface pipe Benefits
cls initdb.py p0.py <input\fred.f >f1.txt type f1.txt | indb.py NodeToken >f2.txt type f2.txt | s3 ars.db call s3 ars.db "select * from NodeTokens" call s3 ars.db "select count(*) from NodeTokens" type f1.txt | only.py NodeToken >f3.txt outdb.py -n ars.db NodeTokens | parse.py numdb.py ars.db NodeTokens Sample
Software Complexity Programmer Understandability Maintainability Reduce by tools Reduce by techniques FSMs can be everywhere
