A string is a finite sequence of symbols. We use a letter, such as w , to denote a string. If w is the string, then the length of string is denoted as w , and it is a count of number of symbols of w . For example, if w = xyz , w = 3. If w = 0, then the string is called an "empty" string, and we use ˆˆ to denote the empty string.
A string's prefix is the string formed by taking any number of leading symbols of string. For example, if w = abc , then ˆˆ , a , ab , and abc are the prefixes of w . Any prefix of a string other than the string itself is called a "proper" prefix of the string.
A string's suffix is formed by taking any number of trailing symbols of a string. For example, if w = abc , then ˆˆ , c , bc , and abc are the suffixes of the w . Similar to prefixes, any suffix of a string other than the string itself is called a "proper" suffix of the string.
If w 1 and w 2 are two strings, then the concatenation of w 1 and w 2 is denoted as w 1 . w 2 ”simply, a string obtained by writing w 1 followed by w 2 without any space in between (i.e., a juxtaposition of w 1 and w 2 ). For example, if w 1 = xyz , and w 2 = abc , then w 1 . w 2 = xyzabc . If w is a string, then w . ˆˆ = w , and ˆˆ . w = w . Therefore, we conclude that ˆˆ (empty string) is a concatenation identity.
An alphabet is a finite set of symbols denoted by the symbol & pound ; .
A language is a set of strings formed by using the symbols belonging to some previously chosen alphabet. For example, if = { 0, 1 }, then one of the languages that can be defined over this will be L = { ˆˆ , 0, 00, 000, 1, 11, 111, }.
A set is a collection of objects. It is denoted by the following methods :
We can enumerate the members by placing them within curly brackets ({ }). For example, the set A is defined by: A = { 0, 1, 2 }.
We can use a predetermined notation in which the set is denoted as: A = { x P ( x ) }. This means that A is a set of all those elements x for which the predicate P ( x ) is true. For example, a set of all integers divisible by three will be denoted as: A = { x x is an integer and x mod 3 = 0}.
Union: If A and B are the two sets, then the union of A and B is denoted as: A ˆ B = { x x in A or x is in B }.
Intersection: If A and B are the two sets, then the intersection of A and B is denoted as: A ˆ B = { x x is in A and x is in B }.
Set difference: If A and B are the two sets, then the difference of A and B is denoted as: A ˆ’ B = { x x is in A but not in B }.
Cartesian product: If A and B are the two sets, then the Cartesian product of A and B is denoted as: A B = { ( a , b ) a is in A and b is in B }.
Power set: If A is the set, then the power set of A is denoted as : 2 A = P P is a subset of A } (i.e., the set contains of all possible subsets of A .) For example:
Concatenation: If A and B are the two sets, then the concatenation of A and B is denoted as: AB = { ab a is in A and b is in B }. For example, if A = { 0, 1 } and B = { 1, 2 }, then AB = { 01, 02, 11, 12 }.
Closure: If A is a set, then closure of A is denoted as: A * = A ˆ A 1 ˆ A 2 ˆ ˆ A ˆ , where A i is the i th power of set A , defined as A i = A.A.A i times.
(i.e., the set of all possible combination of members of A of length 0)
(i.e., the set of all possible combination of members of A of length 1)
(i.e., the set of all possible combinations of members of A of length 2)
Therefore A * is the set of all possible combinations of the members of A . For example, if = { 0,1), then * will be the set of all possible combinations of zeros and ones, which is one of the languages defined over .