List of Important Symbols – Formal Languages and Automata Theory

List of Important Symbols

Symbol

Meaning

Section in which the symbol and its explanation appear first

a ∈ A

a belongs to the set A

1.1

a ∉ A

a does not belong to the set A

1.1

Ø

Empty set (Phi)

1.1.2

If and only if

1.1.3

|A|

Cardinality of A

1.1.3

A ⊆ B

A is a subset of the set B

1.1.4

A ⊂ B

A is proper subset of the set B

1.1.4

℘(A)

Power set of A

1.1.5

A ∪ B

Union of sets A and B

1.1.6

A ∩ B

Intersection of sets A and B

1.1.6

A − B

Complement of B in A

1.1.6

A′

Complement of A

1.1.6

<a, b>

Ordered pair

1.1.10

A × B

Cartesian product

1.1.11

aRb or Rab

a is related to b under the relation R

1.2

R′

Complement of relation

1.2.3

R−1

Inverse of relation R

1.2.3

F(x)

Image of x under f

1.3

F: A → B

Function from A to B

1.3.2

G Ο F

Composition of F and G

1.3.2

idA or IA

identity function on A

1.3.2

Alphabet set

1.4

∑*

Set of all strings over alphabet ∑

1.4

∑+

Set of all strings over non-empty alphabet ∑

1.4

ε

Empty string or epsilon

1.4

(V, T, P, S)

A grammar

1.4.2

α

String of terminals and non-terminals

1.4.3

B

String of terminals and non-terminals

1.4.3

Δ

Transition function

2.1

Q

Set of states

2.1

F

Set of final states

2.1

Belongs to

2.4

Extended transition function

2.6.1

∪ε-closure

Union of null closure of

2.6.1

k

k-Equivalence class

2.8.3

Implies

2.8.2

Δ

Set of output symbols

2.9.1

Λ

Out function

2.9.1

R

Regular expression

3.3

h

Homomorphism function

3.9

A α

A derives α on one or more substitutions

4.10

A ⇒ α

A derives α on single substitutions

4.10

Γ

Stack symbols

5.1.1

Z0

Initial stack symbol

5.1.1

γ

The content of the stack read from top to bottom

5.1.3

(q, x, s) (q, ε, α)

Left configuration derives the right configuration on machine M on one or more derivations

5.4.1

B

Blank symbol on tape

6.1.1

<l, q, r>

Instantaneous description of TM

6.1.2

Check of symbol

6.3.3

#

Special tape symbol

6.5

Ø, $

Special tape-end markers in LBA

6.10

For all values of

Summation series for values of j varying from 1 to n

˥

Negation or NOT

11.2

Conjunction or AND

11.2

Disjunction or OR

11.2

Implication or IF..THEN..

11.2

Biconditional

11.2

Ǝ

There exists

11.8