A B
B
Aa
→
→
There is no language L produced as there is no proper termination.
GLOSSARY
Set: Collection of objects
Singleton: Set having only one element.
Empty set: Set with no element
Complement: Set containing everything not contained in the base set.
Cardinality: Number of elements in a set.
Powerset: Set having ‘n’ elements have a powerset having 2
n elements.
Relation: A relation on two sets is a set of ordered pair.
Poset: Partially ordered set.
Mapping: A function is otherwise called Mapping.
Injection (one-to-one function): Function is one-to-one if different elements
in domain of one set have distinct images in the range.
Surjection (onto function): A function is onto function if each element of a
set is the image of some element of the other set.
Bijection (one-to-one onto function): Function that is both one-to-one and
onto
Invertible function: Function is invertible if and only if it is both one-to-one
and onto.
Degree of vertex: Number of edges having that vertex as an end point.
Loop: Graph having an edge from a vertex to itself.
Isolated vertex: Vertex with zero as degree.
Directed graph: Graph having arrows instead of lines.
Outdegree: Number of arrows pointing from a particular node.
Indegree: Number of arrows pointing to a particular node.
Alphabet: Finite set of symbols.
String: Finite sequence of symbols from an alphabet.
Lexicographic ordering: Dictionary ordering, except that shorter strings
precede longer strings.
Language: Any set of strings over an alphabet.
Kleene star: Set of all strings obtained by concatenating zero or more strings
from a language.
Boolean logic: System built with two values True and False.
Negation: Means NOT operation
Conjunction: Means AND operation
Disjunction: Means OR operation.
Introduction
43
B
Aa
→
→
There is no language L produced as there is no proper termination.
GLOSSARY
Set: Collection of objects
Singleton: Set having only one element.
Empty set: Set with no element
Complement: Set containing everything not contained in the base set.
Cardinality: Number of elements in a set.
Powerset: Set having ‘n’ elements have a powerset having 2
n elements.
Relation: A relation on two sets is a set of ordered pair.
Poset: Partially ordered set.
Mapping: A function is otherwise called Mapping.
Injection (one-to-one function): Function is one-to-one if different elements
in domain of one set have distinct images in the range.
Surjection (onto function): A function is onto function if each element of a
set is the image of some element of the other set.
Bijection (one-to-one onto function): Function that is both one-to-one and
onto
Invertible function: Function is invertible if and only if it is both one-to-one
and onto.
Degree of vertex: Number of edges having that vertex as an end point.
Loop: Graph having an edge from a vertex to itself.
Isolated vertex: Vertex with zero as degree.
Directed graph: Graph having arrows instead of lines.
Outdegree: Number of arrows pointing from a particular node.
Indegree: Number of arrows pointing to a particular node.
Alphabet: Finite set of symbols.
String: Finite sequence of symbols from an alphabet.
Lexicographic ordering: Dictionary ordering, except that shorter strings
precede longer strings.
Language: Any set of strings over an alphabet.
Kleene star: Set of all strings obtained by concatenating zero or more strings
from a language.
Boolean logic: System built with two values True and False.
Negation: Means NOT operation
Conjunction: Means AND operation
Disjunction: Means OR operation.
Introduction
43