CSE SOLUTION SITE



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

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.


© Copyright & reserved CSE Solve