CHAPTER 4 Flashcards
(14 cards)
…………..is a relatively self-operating machine or
control mechanism designed to automatically follow a sequence of
operations or respond to predetermined instructions
automaton
T/F The term “self-operating” implies that the automaton can
execute its operations without continuous external intervention.
T
T/F Automata are often characterized by their ability to follow a
sequence of operations. These operations are predefined and
determine the behavior of the automaton.
T
………..is an abstract model of a computer that reads an input string and changes its internal state depending on the current input symbol
Finite state automate(FSA)
T/F The change from one state to another is called a
transition
T
T/F The FSA can change from one state to another in
response to some inputs
T
T/F A FSA is similar to a compiler in that:
– A compiler recognizes legal programs in some (source)
language.
– A finite-state machine recognizes legal strings in some language.
T
T/F A finite state automaton over an alphabet is illustrated
by a state diagram:
T
T/F An FSA is defined by:
1- a list of its states
2- its initial state (start state)
3-the inputs that trigger each transition (alphabet)
4- set of final states
T
………………is basically a tabular representation of the transition function.
transition table
Types of finite-state automata
Deterministic FSA (DFA)
Nondeterministic FSA (NFA)
…………….For each pair of state and input value there is a unique next state given by transition function.
Deterministic FSA (DFA)
………………For each pair of state and input value there may be several possible next states given by transition
function.
Nondeterministic FSA (NFA)
