4.2 Finite State Machines Flashcards
(26 cards)
What is a finite state machine ?
A computational model for a machine that is always in a fixed state
What’s special about FSM’s ?
Has a finite number of states and can only ever be in one state at a point in time
What are transition rules ?
Rules that describe what a FSM should do given certain criteria
How are states represented in state transmission diagram ?
Circles
How are transitions represented in state transmission diagram ?
Arrows
How are accepting state represented in state transmission diagram ?
Double Circle
What is a common example of FSMs ?
Parity Check
What is a graph ?
An abstract data structure representing complex relationships
What is a weighted graph ?
A graph where edges may have weights indicating a cost of traversal
What is a Vertex/Node ?
A fundamental part of graph where edges connect
What is an Edge/Arc ?
A connection between two vertices in a graph
What is an Undirected Graph ?
A graph where edges are bidirectional and there are no arrows indicating direction.
What is a Directed Graph ?
A graph where edges have a direction indicating a one-way connection.
What is an Adjacency Matrix ?
A way to represent a graph using a matrix to indicate connections between vertices
Each column and row represents a node and the item at [row,column] indicates a connection
What is an Adjacency List ?
A way to represent a graph using a list where each vertex has a list of connected vertices.
A list of nodes is created and each node points to a list of adjacent nodes.
What is a Bidirectional Edge ?
An edge is an undirected graph that allows traversal in both directions
What is an Unweighted Graph ?
A directed graph that has no weights associated with its edges
What are typical uses of graphs ?
Applications such as networking and routing
What is the Cost of Traversal ?
The weight associated with an edge in a weighted graph .
What is a Directed Graph ?
A graph where all edges are one-way.
How is an Unweighted Graph represented in an adjacency matrix ?
Connections can be represented by a 1
How is a Weighted , undirected graph represented in an adjacency matrix ?
The matrix is symmetric and the entries represent the weights of the edges.
What is a sparse graph ?
A graph with not many connections(edges), leaving cells empty , wasting memory space.
How could a weighted graph be represented in code ?
Dictionary of Dictionaries where each key being the node and the value being a dictionary of adjacent nodes and edge weights
