Elements and Sets in Mathematics

Elements and Sets

• An element is a well-defined object.
• A set is a collection of well-defined objects, represented by a capital letter.

Method of Set Notation

• Roster/Tabular/List Method: represents a set by listing its elements, separated by commas and enclosed in curly brackets.
• Set Builder/Rule Method: defines a set by stating a property that characterizes all its elements.

Types of Sets

• Finite Set: a set with countable elements.
• Infinite Set: a set with uncountable elements.
• Empty Set (Null or Void Set): a set with no elements, denoted by {}.
• Unit Set (Singleton): a set with only one element.
• Subset: every element of set A is also an element of set B, denoted by A ⊆ B.
• Proper Subset: at least one element in B is not contained in A, denoted by A ⊂ B.
• Family Set: a class of sets or the set of sets.
• Power Set: the set of all subsets of a given set, denoted by P(A).
• Universal Set: a set that contains all objects, including itself.

Cardinality

• The number of elements in a set.

Set Relations

• Equal Sets: same elements and same cardinality.
• Equivalent Sets: same cardinality.
• Disjoint Sets: no common elements, different cardinalities.

Set Operations

• Union: contains all elements of the sets involved.
• Intersection: contains exactly the common elements of the sets involved.
• Set Difference: contains everything in the minuend but not in the subtrahend.

Relations

• A relationship between elements of two sets.
• Types of Relations:
  • Reflexive Relation: every element is related to itself.
  • Symmetric Relation: any element pair is related to each other.
  • Transitive Relation: if one element is related to a second, and the second is related to a third, then the first element is also related to the third.
  • Equivalent Relation: a relation that is reflexive, symmetric, and transitive.

Functions

• A way of matching members from set "A" to set "B".
• Injective Function: one-to-one relationship.
• Surjective Function: each element of B has a pair.
• Bijective Function: both injective and surjective.
• Inclusion Function: domain is a subset of its codomain.

Graph Theory

• A bunch of vertices (Nodes) represented by circles, connected by edges represented by lines.
• Tree: an undirected graph, any two vertices are connected by exactly one simple path, and does not contain a cycle.
• Adjacent Vertices: a pair of vertices that determine an edge are "adjacent" vertices.
• Circuit: a path that begins and ends at the same vertex.
• Simple Path: no vertex appears more than once in the vertex sequence.
• Connected Graph: there is a path from any vertex to any other vertex in the graph.
• Disconnected Graph: there is no path from any vertex to any other vertex in the graph.
• Component: occurs only to disconnected graphs, connected pieces of the graph.
• Simple Cycle: one that does not repeat any node except for the first and last.

Automata Theory (Theory of Computation)

• A theoretical branch of computer science, established during the 20th century.
• Pure mathematics of computer science, theory of what can and cannot be computed.

History of Automata

• 1936: First Infinite Model by Alan Turing
• 1943: First description of finite automata by Warren McCulloch and Walter Pitts
• 1955: Generalized Automata Theory for Machines by G.H.Mealy and E.F.Moore

Alphabet and String

• Alphabet: a finite, nonempty set of symbols, denoted by Σ.
• String: a list of symbols from an alphabet.

Language

• A set of strings from the same alphabet.

Finite Automate

• A state diagram that comprehensively captures all the possible states and transitions that a machine can take as a response to inputs.
• Recognizer for "Regular Languages".

Deterministic Finite Automaton (DFA)

• An automaton that cannot be in more than one state at any one time.
• Does not accept empty strings.

Nondeterministic Finite Automaton (NFA)

• An automaton that may be in several states at once.
• Allows zero, or more for every input symbol.

State Diagram (Transition Graph)

• A directed graph where vertices represent the internal state of the automaton, and the edges represent the transitions.

Dead State

• A non-final state that transits itself for all input symbols.

Regular Expression

• A simple expression that describes the languages accepted by a FA.
• Sequence of characters that forms a search pattern, mainly for use in pattern matching with strings or string matching.

Regular Set

• A set accepted by a finite automaton.

Closure

• A set is closed under an operation if, whenever the operation is applied to members of the set, the result is also a member of the set.

Operators of Regular Expression

• Union: set of strings that are in either L1 or L2, or both.
• Concatenation: set of strings formed by taking any string and concatenating it with any string.
• Kleene Closure(*): set of strings that can be formed by taking any number of strings, including the null string.
• Positive Closure(+): set of strings that can be formed by taking any number of strings, excluding the null string.

Moore Machines

• Its output depends only on the present state.
• Considered as "counting machine".
• Has 6 tuples: Q, q0, Σ, O, δ, and λ.

Mealy Machine

• Its output depends only on the present state and current input symbol.
• Considered as "output producer".

Context-Free Grammar (CFG)

• Also known as Backus-Naur Form (BNF).
• Has 4 tuples: V, T, S, and P.

Derivation [of strings]

• Generation of language using specific rules.

Regular Grammar

• Right Linear Grammar: non-terminal symbol appears at the end of the production.
• Left Linear Grammar: non-terminal symbol appears at the beginning of the production.

Derivation Tree

• Also known as Parse Tree.
• An ordered rooted tree that graphically represents the semantic information of strings derived from CFG.

Approach to Draw a Derivation Tree

• Top-down Approach: starts with the starting symbol, then goes down to tree leaves using productions.
• Bottom-up Approach: starts from tree leaves, then proceeds upward to the root (starting symbol).

Sentential Form

• Partial derivation tree contains the root.

Types of Derivation Tree

• Left Derivation Tree: obtained by applying production to the leftmost variable in each step.
• Right Derivation Tree: obtained by applying production to the rightmost variable in each step.

Ambiguous Grammar

• Grammar where exists two or more derivation trees for some strings.

Simplification

• Reduction of CFG.
• Elimination of production rules and symbols that are not needed for derivation of strings.

Chomsky Normal Form (CNF)

• A context-free grammar where every production rule is of the form: A -> BC or A -> a.

Greibach Normal Form (GNF)

• For every CFL without epsilon, there exists a grammar in which every production is of the form: A → aV where A is a variable, a is exactly one terminal, V is the string of none or more variables.

Pushdown Automata (PDA)

• A way to implement a context-free grammar in a similar way that a DFA is designed for a regular grammar.
• Can remember infinite amount of information.
• Equal to NFA with a stack.

Instantaneous Description

• Represented by a triplet (tuples): q, w, and s.

Turnstile Notation

• Used for connecting pairs of ID’s that represent one or many moves of a PDA.
• Denoted by "⊢".

Parsing

• Used to derive a string using the production rules of a grammar.
• Top-Down Parser: starts from the top with the start-symbol.
• Bottom-Up Parser: starts from the bottom and comes to the start symbol.

Turing Machine

• Proposed by Alan M. Turing (1912-1954).
• A hypothetical machine in 1936 whose computations are intended to give an operational and formal definition of the intuitive notion of computability in the discrete domains.
• Mathematical model which consists of an infinite length tape divided into cells on which input is given.

6 Types of Fundamental Operations

• Read
• Write
• Move tape left
• Move tape right
• Change state
• Halt