ABSTRACT
This chapter reviews rudimentary concepts from logic, set theory, discrete mathematics, and graph theory. For readers familiar with these concepts, it can be treated as a reference for notation and definitions. In general, a formal mathematical systems consists of basic symbols, formation rules, axioms, and inference rules. Basic symbols, such as constants and operators, form components of statements, which are composed according to formation rules. Axioms are primitive statements, whose validity is accepted without justification. By inference rules, some statements infer other statements. A sequence is a list of elements from some universe. A sequence is finite if it consists of finitely many elements; otherwise, it is infinite. Just like set theory has its naive notions, so does formal language theory. Indeed, it automatically assumes that there exists a pre-specified infinite set, referred to as a universal alphabet, whose members are called symbols.
