3 - finite state automata Flashcards
it is a
theoretical model in computer science
and mathematics used to describe and
analyze systems that exhibit discrete and
sequential behavior.
finite automaton/
finite state machine (FSM),
A. 6 components of finite state machine
states
transition’
input alphabet
start state
accept state
other FSM details
A finite set of discrete states, typically represented as circles or
nodes in a diagram. These ______ represent different conditions or
configurations that the automaton can be in at any given moment.
states
A set of _______ or edges between states, typically
represented as arrows in a diagram. _______ define how the automaton
moves from one state to another based on input symbols or conditions.
transition
A finite set of symbols, known as the _______ _______, which
are used to trigger transitions between states. The automaton reads these
symbols one at a time and changes its state accordingly.
input alphabet
The initial state from which the automaton begins its operation
when it is given an input.
start state
One or more states designated as _____ _______ or final
states. When the automaton reaches an ______ ________ after processing the
input, it signifies that the input is accepted or recognized by the automaton.
accept state
A _____ is a basic unit of information or a character from a finite
set of characters.
In the context of FSMs,it is the individual elements that
make up the input alphabet. These can be letters, digits,
or any other characters relevant to the problem being modeled by
the FSM.
symbols
The _______, often denoted as Σ, is the finite set or collection of
symbols from which input strings are constructed for an FSM.
alphabet
A ______ is a sequence of symbols from the alphabet.
- In the context of FSMs, it is an input sequence that the FSM
processes. It is formed by concatenating symbols from the
alphabet in a specific order.
- For example:
o In the binary alphabet Σ = {0, 1}, the string “11010” is
formed by concatenating the symbols ‘1’, ‘1’, ‘0’, ‘1’, and ‘0’.
string
A _______ is a set of strings defined over an alphabet.
- In the context of FSMs, it is a collection of strings that
an FSM can recognize or generate. it is typically
specified in terms of the alphabet and the rules that define which
strings belong to the language.
- For example:
o In the binary alphabet Σ = {0, 1}, the language L1 may
consist of all strings with an even number of ‘1’s, such as
{“”, “0”, “00”, “1100”, “101010”}.
o In the alphabet Σ = {a, b}, the language L2 may consist of
all strings that start with ‘a’ and end with ‘b’, such as {“ab”,
“acb”, “aabb”, “abab”}.
language
It is often denoted as Σ, refers to the set of all possible strings
that can be constructed using the symbols from a given alphabet
Σ. In other words, Σ represents the set of all finite-length strings
composed of symbols from the alphabet Σ, including the empty
string (ε).
Powers of Σ
Refers to the “size” or “number of elements” in a set. It is a way
of quantifying the size of a set or a collection of objects.
- Usually denoted by Σn
= 2n
- Applies to both finite and infinite sets. Finite sets have a finite
cardinality (a specific number of elements), while infinite sets
have infinite cardinality (countably or uncountably infinite). - For examples:
o The cardinality of the set {1, 2, 3} is 3, as it contains three
elements.
o Σ*
= Σ0
U Σ1
U Σ2
U Σ3
= { ε } U { 0,1 } U { 00,01,10,11 } U …
= set of all possible strings of lengths over { 0,1 } (infinite)
cardinality
B. 2 variation of finite state automata
- Deterministic Finite Automaton (DFA)
- Nondeterministic Finite Automaton (NFA)
in _______, for each state and input
symbol, there is exactly one transition
to another state. particularly well-suited for recognizing regular languages.
deterministic finite automaton (DFA)
