advertisement

advertisement

Information about Theoryofcomp science

Theory of

Computer Scince

Computer Scince

advertisement

qwertyuiopasdfghjklzxcvbnmqwertyui opasdfghjklzxcvbnmqwertyuiopasdfgh jklzxcvbnmqwertyuiopasdfghjklzxcvb nmqwertyuiopasdfghjklzxcvbnmqwer tyuiopasdfghjklzxcvbnmqwertyuiopas dfghjklzxcvbnmqwertyuiopasdfghjklzx cvbnmqwertyuiopasdfghjklzxcvbnmq wertyuiopasdfghjklzxcvbnmqwertyuio pasdfghjklzxcvbnmqwertyuiopasdfghj klzxcvbnmqwertyuiopasdfghjklzxcvbn mqwertyuiopasdfghjklzxcvbnmqwerty uiopasdfghjklzxcvbnmqwertyuiopasdf ghjklzxcvbnmqwertyuiopasdfghjklzxc vbnmqwertyuiopasdfghjklzxcvbnmrty uiopasdfghjklzxcvbnmqwertyuiopasdf ghjklzxcvbnmqwertyuiopasdfghjklzxc

Theory of Computer Science 1.Differentiate between Recursive Functions and growth functions Recursion is the technique of defining a function, a set or an algorithm in terms of itself. That is, the definition will be in terms of previous values. Definition A function f: N → N, where N is the set of non-negative integers is defined recursively if the value of f at 0 is given and for each positive integer n, the value of f at n is defined in terms of the values of f at k, where 0 ≤ k < n. Observation: f defined (above) may not be a function. Hence, when a function is defined recursively it is necessary to verify that the function is well defined. Example The sequence 1, 4, 16, 64, ... , can be defined explicitly by the formula f(n) = 4n for all integers n ≥ 0. The same function can also be defined recursively as follows: f(0) = 1, f(n + 1) = 4f(n), for n > 0 To prove that the function is well defined we have to prove existence and uniqueness of such function. In this case, existence is clear as f(n) = 4n. Theorem: (Recursion Theorem): Let F is a given function from a set S into S. Let s0 be fixed element of S. Then there exists a unique function f: N → N where N is the set of non-negative integers satisfying i) f(0) = s0 ii) f(n + 1) = F(f(n)) for all integers n € N. (Here the condition (i) is called initial condition and (ii) is called the recurrence relation). Example Define n! recursively and compute 5! recursively. Solution: We have f: N → N. Then i) f(0) = 1 ii) f(n + 1) = (n + 1)f(n) for all n 0. Clearly f(n) = n!. Now we compute 5! recursively as follows: 5! = 5. 4! = 5. 4. 3! M.C.A vth semester Page 2

Theory of Computer Science = 5. 4. 3. 2! = 5. 4. 3. 2. 1! = 5. 4. 3. 2. 1. 0! = 5. 4. 3. 2. 1. 1 = 120. Note Any sequence in arithmetic progression or geometric progression can be defined recursively. Consider the sequence a, a + d, a + 2d, …. Then A(0) = a, A(n + 1) = A(n) + d. Consider another sequence a, ar, ar2, … . Then G(0) = a, G(n +1) = r G(n). Definition The Fibonacci sequence can be defined recursively as i) F0 = 1 = F1 ii) Fn+1 = Fn + Fn-1 for n > 1. Then F2 = F1 + F0 = 2 F3 = F2 + F1 = 3 F4 = F3 + F2 = 5 ….. Here, there are two initial conditions. Example: Define F(x) = {x/2 when x is even { x-1/2 when x is odd Solution: Define f: N → N such that f(0) = 0 and f(x + 1) = x – f(x). Then f(6) = 5 – f(5) = 5 – [4 – f(4)] = 5 – 4 + [3 – (3)] = 5 – 4 + 3 – 2 + [1 – f(1)] = 5 – 4 + 3 – 2 +1 – [0 – f(0)] = 3. and f(5) = 4 – f(4) = 4 – [3 - f(3)] = 4 – 3 + 2 - [1-f(1)] = f – 3 + 2 -1 + [0 – f(0)] = 2. Growth Functions The growth of a function is often described using a special notation, O-notation (read as “big-oh notation”). It provides a special way to compare relative sizes of functions that is very useful in M.C.A vth semester Page 3

Theory of Computer Science M = (Q = {q0, q1, q2}, = {0, 1}, , q = initial state, F = {q1}), where is given by 0 (q , 0) = q0, 0 (q , 1) = q1, 0 (q , 0) = q0, 1 (q , 1) = q2, 1 (q , 0) = q2, 0 2, 1) = q1. (q Representation of DFA using Transition table: In this method, the DFA is represented in the tabular form. This table is called transitional table. There is one row for each state, and one column for each input. Since, in the transition diagram shown in the fig., there are three states, there are three rows for each state. The input symbols are only 0 and 1 so, there are two columns for the input symbols. The transitional table for the diagram is given below. 5. Differentiate between Moore machine and Mealy machine. The automata systems we have discussed so far are limited to binary output. That is, the systems can either accept or reject a string. In thosesystems, this acceptability is decided based on the reachability of the initial state to the final state. This property of the system produces restrictions in choosing outputs from some other alphabet, then output. You can remove this constraint using both the Moore and Mealy machine, which help in generating an output from a certain output alphabet. Let us denote the output function with the symbol . Thus, when the output of an automata system is dependent only on the present state, then, Output = (q(t)), where q(t) is the present state. The above automata system is called a Moore machine. Alternatively, when the output of the automata system is dependent on both the present input and the present state, then, Output = (q(t), x(t)), where q(t) is the present state and x(t) is the present input. The above automata system is called a Mealy machine. Since the output of a Mealy machine is dependent on both the input and the present state, no output is generated when the input is a null string. This implies that when the input is , the output is also . However, in case of the Moore machine, there is some output of the Moore M.C.A vth semester Page 8

Theory of Computer Science machine only dependent on the present state and not on the present input. Hence, when the input to a Moore machine is , the output is (q). 0 Definition A Moore machine can be with a 6-tuple (Q, , , , ,0) where: q Q is non-empty, finite set of states. is non -empty, finite set of input alphabet. is the output alphabet is transition function, which is a mapping from Q into Q. is the output function mapping Q into q0 Q is the start state. Conversion of Moore Machine into Mealy machine The procedure of converting a Moore machine into a Mealy Machine is very simple. From the given Moore machine state table, you need to transform each column of inputs into the pairs of the next state and the output. The output for a particular state in a pair can be determined by observing the outputs in first table (Moore machine). If, after converting table to this format, it is observed that for any two of the present state the other values in the row are identical, then we can delete one of the states. Let us now consider a few examples to convert a given Moore machine into a Mealy machine. Example Convert the Moore machine M1 whose state table is given in table into and equivalent mealy machine. Moore machine Present State Next state Input a = 0 q0 q1 q2 q3 q1 q3 q2 q0 Output Input a = 1 q2 q2 q1 q3 1 0 1 1 Conversion of Mealy machine into Moore Machine Consider the following steps Step 1: For a state qi determine the number of different outputs that are available in state table of the Mealy machine. Step 2: If the outputs corresponding to state qi in the next state columns are same, then retain state qi as it is. Else, break qi into different states with the number of new states being equal to the number of different outputs of qi. Step 3: Rearrange the states and outputs in the format of a Moore machine. The common output of the new state table can be determined by examining the outputs under the next state columns of the original Mealy machine. Step 4: If the output in the constructed state table corresponding to the initial state is 1, then this specifies the acceptance of the null string by Mealy machine. Hence, to make both the Mealy and Moore machines equivalent, we either need to ignore the output corresponding to the null string or we need to insert a new initial state at the beginning whose output is 0; the other row elements in this case would remain the same. M.C.A vth semester Page 9

Theory of Computer Science 6. Define context-free grammar. What is an ambiguous grammar? Explain with an example. Definition A grammar G is a quadruple G = (VN, VT, , S), where VN is set of variables or non-terminals VT is set of terminals symbols @ is set of productions S is the start symbol, is said to be type 2 grammar or context free grammar (CFG) if all the productions are of the form A →α, where α € (VN u VT)* and A € VN. The symbol (indicating NULL string) can appear on the right hand side of any production). The language generated from this grammar is called type-2 language or context free language (CFL). Observations: 1. There is only one symbol A on the left hand side of the production and that symbol must be a non-terminal. 2. α € (VN u VT)* implies that right hand side of the string may contain any number of terminals and non-terminals including (NULL string). 3. Every regular grammar is a CFG and hence a regular language is also context free language but the reverse is not true always. 4. Notation: nx(w) = number of x‟s in the string w. Example Let G = (VN, VT, , S) be a CFG, where VN = {S} VT = {a, b} : S → aSa | bSb | S: Starting symbol. Find the language generated by this grammar Solution: The null string can be obtained by applying the production S → so that S => . S => aSa (applying S → aSa) => abSba (applying S → bSb) => abbSbba (applying S → bSb) => abbbSbbba (applying S → bSb) => abbbbbba (applying S → ). Therefore, by applying the productions S → aSa and S → bSb, and any number of times and in any order, finally applying the production S → aSa, we get a string w followed by reverse of it (say wR). M.C.A vth semester Page 10

Theory of Computer Science Hence, the language generated by this grammar is L = {wwR | w € {a + b}*}. Since this language is generated from the context free grammar, it is a context free language. Example Show that the language L = {ambn|m ≠ n} is context free. Solution: It is clear from the given language that a number of a‟s are followed by n number of b‟s and number of a‟s and b‟s are not equal. As a first attempt, we can have the production S → aSb using which n number of a‟s are followed by one S followed by n number of b‟s are generated. Now, if we replace the non-terminal S by the production S -> AB we get n number of a’s followed by n number of b’s. But, we should see that number of a‟s and b‟s are different. So, we should be in a position to generate either one or more extra a‟s or one or more extra b‟s. Hence, instead of the production S we can have productions SAB From the non-terminal A, we can generate one or more a‟s and from non-terminal B, we can generate one or more b‟s as shown below: A aA a B bB b. So, the context free grammar G = (VN, VT, , S), where VN = {S, A, B}, VT = {a, b}, : S aSb A B A aA a B bB b S: starting symbol, which generates the language L = {ambn Since a CFG exists for the language, the language is m n}. context free. Example Obtain a Context free grammar on {a, b} to generate a language L = {anwwRbn|w € ∑*, n 1}. Solution: Here, the string wwRmust be enclosed between an and bn where n ≥ 1. The final grammar is VN = (S} VT = {a, b} @: S -> aSb |aAb A -> aAa |bAb| and , S is the start symbol. We will verify, by taking n = 2, so that we generate a string aabaabbb (here w = ba, and that wR = ab). Consider the following sequence of productions to get the string aabaabbb. S => aSb (applying S -> aSb) aaAbb (applying S-> aAb) aabAbbb (applying A-> bAb) aabaAabbb (applying A -> aAa) M.C.A vth semester Page 11

Theory of Computer Science aaba abbb (applying A -> ) aabaabbb. (since an empty string) is Problem Obtain the context free grammar for the regular expression (011 + 1)*(01)*. Solution: The expression (011 + 1)*(01)* is of the form A*B* where A = 001 or 1 and B = 01. The regular expression A*B* means that any number of A‟s (possibly none) are followed by any number of B‟s (possibly none). Any number of A‟s (that is, 011‟s or 1‟s) can be generated using the productions A -> 011A | 1A| Any number of B‟s (that is, 01‟s) can be generated using the productions B -> 01B| Now, the language generated from the regular expression (011 + 1)*(01)* can be obtained by concatenating A and B using the production S -> AB Therefore, the final grammar G = (VN, VT, @, S), where VN: {S, A, B} VT: {0, 1} VT: S -> AB, A -> 011A |1A| B -> 01B | S: start symbol. M.C.A vth semester Page 12

Presentación que realice en el Evento Nacional de Gobierno Abierto, realizado los ...

In this presentation we will describe our experience developing with a highly dyna...

Presentation to the LITA Forum 7th November 2014 Albuquerque, NM

Un recorrido por los cambios que nos generará el wearabletech en el futuro

Um paralelo entre as novidades & mercado em Wearable Computing e Tecnologias Assis...

Microsoft finally joins the smartwatch and fitness tracker game by introducing the...

Rating and reviews for Professor Sinan Kockara from University of Central Arkansas Conway, AR United States.

Read more

This paper studies pipelined algorithms for protecting distributed grid computations from cheating participants, who wish to be rewarded for tasks they receive

Read more

Rating and reviews for Professor Charles Keleman from Swarthmore College Swarthmore, PA United States.

Read more

Goldberg, A.: An Efficient Implementation Of A Scaling Minimum-Cost Flow Algorithm. J. of Algorithms. 22, 1-29 on ResearchGate, the professional network ...

Read more

Kann, V.: On the Approximability of Minimizing Nonzero Variables or Unsatisfied Relations in Linear Systems. Theoretical Computer Science 209(1-2), 237-260

Read more

Uniﬁed Information Gain Measures for Inference Processes JoseHernandez-Orallo1 Universitat Polit`ecnica de Val`encia, Dep. de Sistemes Inform`atics i ...

Read more

View and Download PowerPoint Presentations on COMP M3 PPT. Find PowerPoint Presentations and Slides using the power of XPowerPoint.com, find free ...

Read more

Harry Porter 6[Full DOWNLOAD] Syntax ... A White Paper Overview Harry H. Porter III Department of Computer Science Portland State University March ...

Read more

## Add a comment