2 Data Definitions
A list of symbols representing lowercase letters in the Roman alphabet.
A (listof symbol). Each symbol is a member of the same alphabet.
A string of length one representing a lowercase letter in the Roman alphabet.
An uppercase letter (e.g., A) or a symbol comprised of an uppercase
letter, dash, and number (e.g., A-72431).
A (list state symbol state) representing a transition in a
deterministic finite-state automaton. The symbol must be in the
alphabet of the machine.
A (list state symbol state) representing a transition in a
nondeterministic finite-state automaton. The symbol must either be
in the alphabet of the machine or be EMP.
A (list (list state symbol pop) (list state push)) denoting a
transition in a pushdown automaton. The symbol must be in the
alphabet of the machine. The elements to remove from the
top of the stack are denoted by pop which is either EMP or
a list of symbols where the leftmost is first element to pop.
The elements to place onto the top of the stack
are denoted by push which is either EMP or a list of symbols where
the leftmost symbol is the last element to push.
If an alphabet symbol, it denotes the symbol written to the tape of a Turing
machine. Otherwise, it is the direction in which to move the head:
RIGHT or LEFT.
A (list (list state symbol) (list state tm-action)) representing a
transition in a nondeterministic Turing machine. The symbol must
either be either EMP or an element of the machine’s alphabet.
A (list (list state (listof symbol)) (list state (listof action))) representing
a transition in a nondeterministic multitape Turing machine. The symbols represent what
is read on each of the tapes and must be either EMP or an element of the machine’s
alphabet.
A list containing a state and a word. The word is the unread part of
the input and the state is the current state of the machine.
A list containing a state and a word. The word is the unread part of
the input and the state is the current state of the machine.
A list containing a state, a word, and a list of symbols. The state
is the current state of the machine. The word is the unread part of
the input. The list of symbols is the contents of the stack where
the leftmost symbol is the top of the stack.
A list containing a state, a natural number, and a list of symbols.
The state is the current state of the machine. The natural number is
the head’s position. The list of symbols is the contents of the tape
up to the rightmost position reached, so far, by the machine.
A list containing a state and one or more tape configurations. A tape
configuration is a list containing a natural number for the head’s
position and a sublist representing the contents of the tape.
syntax
A regular expression (see regular expression constructors below).
Lowercase letters.
A set of nonterminal symbols. A nonterminal symbol is an upercase
letter in English: A..Z. That is, FSM programmers are limited to 26 nonterminals.
The internal representation in FSM may use symbols of the form nts-<digit>^+
(e.g., A-72431). Such nonterminals may not be directly used in an FSM program.
A regular grammar rule is a list of
the following form:
(S ARROW EMP)
(N ARROW a)
(N ARROW aB)
S is the starting nonterminal, N and B are nonterminal symbols, and
a is a terminal symbol.
A context-free grammar rule is a list of the
form (A ARROW J), where A is a nonterminal symbol and J is either
EMP or an aggregate symbol of terminals and nonterminals.
A context-sensitive grammar rule is a list of the
form (H ARROW K), where H is an aggregate symbol of terminals and
at least one nonterminal and K is either
EMP or a an aggregate symbol of terminals and nonterminals.
A representation of a statemachine in FSM. A state machine is one of the following:
Deterministic Finite Automaton (dfa)
Nondeterministic Finite Automaton (ndfa)
Pushdown Automaton (pda)
Turing Machine (tm)
Language Recognizer (tm-langauge-recognizer)
Multitape Turing Machine (mttm)
Multitape Turing Machine Language Recognizer (mttm-language-recognizer)
A state machine rule is either a dfa-rule, an ndfa-rule, a
ndpda-rule, or a tm-rule.
A representation of a grammar in FSM. A grammar is one of the following:
Regular Grammar (rg)
Context-Free Grammar (cfg)
Context-Sensitive Grammar (csg)
A grammar rule is either a rrule, a cfrule, or csrule.
A derivation is either a (list nts ARROW nts) or
a (append (list ARROW nts) Derivation).
A composed Turing machine description is either:
empty
(cons tm ctmd)
(cons LABEL ctmd)
(cons symbol ctmd
(cons BRANCH (listof (list symbol ctmd)))
(cons (GOTO LABEL) ctm)
(cons ((VAR symbol) ctm) ctm)
A LABEL is a natural number.
A composed Turing machine.