# CSE SOLUTION SITE

Theory Of Computation Question List | Solve

### (15).Discuss the capabilities of CFG.

Theory Of Computation Question List | Solve

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

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

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

# 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 Alphabets

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.

# Define power of an alphabet

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

# What is Concatenation?with example

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

# What is Language?with example

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

# What is Problem?

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.

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

# What is Graph?with example

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 v1, v2...........vk, k 1, such that there is an edge (vi, vi+1) for each i, 1<=ik, the path is a cycle.

# What is Directed Graph?with example

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, v1, v2...........vk, k 1 such that vi, vi+1 is an are for each i, 1<=i

# What is Tree?with Property

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"

# 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.
```

# What is Context Free Grammar With Example?

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)
```

# Write Down 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.
```

# Discuss the capabilities of CFG

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.