What do mean by relation? Write down the properties of relations.

Relation : A relation is a set of pairs. The first component of each pair is chosen from a set called the domain and the second component of each pair is chosen from a set called the range. If R is a relation and (a,b) is a pair in R, then we often write a Rb

Properties of relation : 

1) We say a relation R on set S is

2) Reflexive if a Ra for all a in S.

3) Irreflexive if a Ra is false for all a in S.

4) Transitive if aRa and bRc imply aRc

5) symmetric if aRa implies bRa

6) Asymmetric if aRb implies that bRa is false.

Learn More from Blog :  

Expert Web Engineering

Expert Computer Networking

Talent Programming Language C

Logical Discrete Mathematics

Expert Compiler Design

Expert Data Structure

Professional Algorithm Design

Professional Responsive Web Page Design By Bootstrap

Talent Software Engineering

Define graphs, directeed graph and trees

Graphs : A graphs denoted G = (V, E), consists of a finite set of vertices V and a set of pairs of n vertices E called edges.

Example : graph is shown in figure-6(a).

Here, V = {1, 2, 3, 4} and E = {(n, m)} | n+m = 4 or n+m = 7}

A path in a graph is a sequence of vertices v₁, v₂...........v_k, k 1, such that

there is an edge (v_i, v_i+1) for each i, 1<=i<k. The length of the path is k-1. if v₁ = v_k, the path is a cycle.

Directed graph : A directed graph also denoted G = (V,E), consist of finite set of vertices V and a set of ordered pairs of vertices E called ares. We denote an are from v to w by v w.

Example : A directed graph appears in figure-6(b).

A path is directed graph is a sequence of vertices, v₁, v₂...........v_k, k 1 such that v_i, v_i+1 is an are for each i, 1<=i<k. We say the path in from v₁ to v_k

Trees : A tree is a directed graph with the following properties :

1) There is one vertex called the root, that has no predecessors and from which there is a path to every vertex.

2) Each vertex others than the root has exactly one predecessor

3)  THe successors of each vertex are ordered "from the left"

Define Inductive proofs and structural inductions

Inductive proofs : A statement that has an integer parameter n can often be proved by induction on a. We prove the statement is true for the basis, a finite number of cases for particular values of n and then prove the induction step : that if the statement is true for values unto n, then it is true for n+1.

Structural Inductions : We may prove a theorem about the construction objects by induction on the number of steps used in its construction. this type of induction is referred to as structural.

Define the following terms : Concatenation of strings, Language, Problems

Define the following terms : 

• Concatenation of strings
  
• Language
  
• Problems

Concatenation of strings : Let x and y be strings. Then  xy denotes the concatenation of x and y, that is , the string formed by making a copy of x and following it by a copy of y. More precisely, if x is the string composed of i symbol ; x = a1 a2.....ai and y is the string composed of j symbols y = b1 b2..........bi, the xy is the string of length, i+j : xy = a1 a2.........ai b1 b2.........bi.

Example : let x = 01101 and y = 110

               Then, xy = 01101110

                And, yx = 11001101

Languages : A set of string all of which are chosen from some summession symbol, where  summession symbol is a particular alphabet, is called Language. If summession symbol is an alphabet, The L is a language over summession symbol. The set of palindromes over the alphabet {0, 1} is an infinite language is the set of all strings over a fixed alphabet summession symbol. We denoted this language by summession symbol.

Example : If summession symbol = {a} then summession symbol = {E, a, aa, aaa.......}

L = {0, 1}, then L = {E, 0, 1, 00, 01, 10, 11, 000.......}.

Problems : In automata theory a problem is the question of deciding whether a given string is a number of some particular languages. More precisely, if summession symbol is an alphabet, and L is a language over summession symbol, then the problem is given a string W in summession symbol, decide whether or not W is in L.  

Define Alphabets and power of an alphabet

Alphabets : An alphabet is a finite nonempty set of symbols. Conventionally we use the symbol summession symbol for an alphabet, common alphabets include :

1. summession symbol = {0,1}, the binary alphabet

2. summession symbol = {a,b...z}, the set of the lower case letters.

3. The set of all ASCII characters or the set of all printable ASCII characters.

Powers of an Alphabet : If summession symbol is an alphabet, we can express the set of all strings of a certain length from that alphabet by using an exponential notation. We  define summession power of k to be the set of strings of length K, each of which symbols is in summession symbol.

Example : If  summession symbol = {0, 1}, then power of 1 summession symbol = {0,1}

                             power of 2 summession symbol = {00, 01, 10, 11}

                            power of 3 summession symbol = {000, 001, 010, 011, 100, 101, 110, 111}

And so on.

What do you mean by prefix and suffix?

Prefix and Suffix : A prefix of a string is any number of leading symbols of that string, and suffix is any number of trailing symbols.

Example : String abc has prefixes E,c,bc and abc, its suffixes are E, c, bc, and abc. 

A prefix or suffix of a string other than the string itself is called a proper prefix or suffix.

Define the following terms with example :

Define the following terms with example :

(i) Symbols : A "symbol" is an abstract entity that we shall not define formally, just as "point" and "line" are not defined geometry

Example : a,b,c etc are alphabetical symbols, 1,2,3 etc are numerical symbols.

(ii) Strings : A string is a finite sequence of symbols chosen from some alphabet.

Example : 01101 is a string from the binary alphabet Summestion = {0,1}

(iii) Empty String : The empty string is the string with zero occurrences of symbols. This string denoted e, is a string that may be chosen from any alphabet. Thus |E| = 0.

(iv) Length of a string : The length of a string W, denoted |W| , is the number of symbols composing the string 

Example : abcd has length 4.