Mathematical notation for the study of computation

See the table of symbols related to computation .

This is a collection of symbols and expressions related to the theory of computation.

See the complete collection of Grafstate symbols .

Discrete math

Below are symbols and expressions from discrete math that are used to define terminology in the theory of computation. This is not a complete notation guide for discrete math.
Symbol
Grafstate code
Context
Description
⋁
\v
Logical expressions
Logical OR∶ x ⋁ y is FALSE if x and y are both FALSE. x ⋁ y is TRUE otherwise.
⋀
\^
Logical expressions
Logical AND∶ x ⋀ y is TRUE if x and y are both TRUE. x ⋀ y is FALSE otherwise.
¬
\!
Logical expressions
Logical NOT∶ ¬TRUE is FALSE. ¬FALSE is TRUE.
∀
\A
Logical statements
The universal quantifier∶ ∀x∈S […] is read for all x in S, […].
∃
\E
Logical statements
The existential quantifier∶ ∃x∈S […] is read there exists some x in S such that […].
∈
\in
Sets
Contained in∶ x ∈ S is read x is contained in S.
∉
\!in
Sets
Not contained in∶ x ∉ S is read x is not contained in S.
⋃
\u
Sets
The union of 2 sets∶ A ⋃ B={x∶x ∈ A ⋁ x ∈ B}.
⋂
\n
Sets
The intersection of 2 sets∶ A ⋂ B={x∶x ∈ A ⋀ x ∈ B}.
A

A⋃B
~A
~{A\uB}
Sets
The complement of a set∶
A
= {x∶x ∉ A}. If U is the universe of A, then
A
= U - A.
-
-
Set
Set A minus set B∶ A-B={x∶x ∈ A ⋀ x ∉ B} = A⋂
B
.
Δ
\D
Sets
The symmetric difference of 2 sets∶ A Δ B = (A-B) ⋃ (B-A).
℘()
\P()
Sets
The power set of a set S (℘(S)) is the set of all subsets of S.
∅
{}
\0
{}
Sets
The empty set
⟶
->
Implications
Logical ONLY IF∶ p ⟶ q is TRUE when ¬p ⋁ q is TRUE. p ⟶ q is FALSE otherwise.
⟹
=>
Implications
Only if statement∶ p ⟹ q can be read if p, then q.
⟺
<=>
Implications
If and only if statement∶ p ⟺ q can be read p if and only if q. The statement p ⟺ q is equivalent to the following pair of statements∶
     p ⟹ q.
     q ⟹ p.

The statement p ⟺ q is also equivalent to the following pair of statements∶
     p ⟹ q.
     ¬p ⟹ ¬q.

Glyphs

Below are some Grafstate Glyphs that are related to the study of computation∶
Glyph
Grafstate code
Context
Description
@{base}
Recursive definitions
The base step
@{loop}
Recursive definitions
The recursive step
@{state}
Automata
A state
@{stack}
PDAs
The stack
@{taoe}
Turing machines
The tape
@{steps}
Processes
The steps
@{yes}
Statements
True statement
Completed proof
@{no}
Statements
Contradiction

Computational structures

Symbol
Grafstate code to type the math
Grafstate code to create a structure
Context
Description
Q
Q
Q
Automata
The set of states
δ
\d
d
Automata
The transition function
Σ
\S
S
Automata
The input alphabet
Τ
\T
T
1PDAs
2 Turing machines
1The stack alphabet
2 The tape alphabet
q0
q_0
q0
Automata
The initial state
F
F
F
Automata other than Turing machines
The set of final state
qa
q_a
qa
Turing machines
The accept state
qr
q_r
qr
Turing machines
The reject state
V
V
V
Grammars
The set of variables
v0
v_0
v0
Grammars
The initial variable
⟶
->
->
Grammar rules
A rule in a CFG or a PSG defines how to expand a variable Var to ε or to a sequence of variables in V and symbols in Σ.
∣
|
|
Grammar rules
Multiple rules expanding a single variable can be written on one line if the expansions are separated by the ∣ symbol.
⟹
=>
na
Leftmost derivations
Each derivation step in a leftmost derivation describes the expansion of one variable by one rule.
\GSSYM derives ;
|-
na
Grammars
Grammar G derives string w (G\GSSYM derives ;w).
≅
~=
na
Automata and grammars
Automata M1 and M2 are equivalent (M1 ≅ M2) if L(M1) = L(M2). Grammars G1 and G2 are equivalent (G1 ≅ G2) if L(G1) = L(G2). Automaton M and grammar G are equivalent (M ≅ G) if L(m) = L(G).
δ*
\d*
na
DFAs
The δ* function defines the process of computation for a DFA. δ* is defined by the following recursive definition∶
∀q∈Q δ*(q,ε)=q.
∀q∈Q ∀w∈Σ* ∀c∈Σ, δ*(q,cw) = δ*(δ(q,c),w).
ec()
ec()
na
NFAs
The ε-closure of a state is defined by the following recursive definition∶
∀q∈Q, q ∈ ec(q).
∀qi∈Q ∀qj∈ec(qi) ∀qk∈Q [qk∈δ(qj,ε) ⟶ qk∈ec(ei)].