.Define the following terms with example : (i)Symbols (ii)String(iii)Empty String(iv)Length of a string

(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)String :

A string is a finite sequence of symbols chosen from some alphabet.

Example :

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

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.(iii)Empty String :

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

abcd has length 4.Example :

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.

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.

Power 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

Concatenation :

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.......}.

Problem :

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.

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.

Graph :

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_{1}, v_{2}...........v_{k}, k 1, such that there is an edge (v_{i}, v_{i}+1) for each i, 1<=ik, 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_{1}, v_{2}...........v_{k}, k 1 such that v_{i}, v_{i}+1 is an are for each i, 1<=i

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"

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.

Context Free Grammar With Example :

A CFG is a way of describing language by recursive rules. A CFG consists four tuples, denoted G = {V, T, P, S} Where, V = Finite set of variables. [Eg. {S, E}etc.] T = Finite set of terminals. [Eg. {a, b, c,+}etc.] P = Finite set of productions. [Eg. E E+E] S = Start symbol. Example : Let a CFG which is given : Here, V = {E} T = {+, *, id} S = E So, the grammar notation is written as; G = (E, {+, *, id}, P, E)

The Advantages of CFG :

A grammar give a precise, yet easy to understand, syntactic specification of a programming language. An efficient parser can be constructed automatically from a properly designed grammar. A grammar imparts a structure to a program that is useful for its translation into object code for the detection of errors. Language ecvolved over a period of time.acquiring new constructs & performing additional tasks.

The capabilities of CFG :

Context free grammars are capable of describing most of the syntax of programming language. suitable grammars for expressions can often be constructed using associatively & precedence information. So, context free grammar are most useful in describing nested structures such as balanced parentheses, matching begin-end's, corresponding if-then-else's & so on. These nested structures cannot be described by regular expression. The following grammars the string, which serves the language. Stat if cond then stat | if cond then stat else stat |other -stat.