THEORY OF COMPUTER SCIENCE

Question1. Differentiate between Recursive Functions and growth functions.

Answer. Recursive Functions
Recursive is that the technique of defining a function, a group or an algorithm in terms of itself. That is, the definition is going to be in terms of previous values.

Definition
A function f: N → N, where N is that the set of non-negative integers is defined recursively if the worth of f at 0 is given and for every positive integer n, the worth of f at n is defined in terms of the worth of f at k, where 0 ≤ k < n.

Observation: f defined might not be a function. Hence, when a function is defined recursively it's necessary to verify that the function is well defined.

Example.
The sequence 1, 4, 16, 64, … , are often defined explicitly by the formula f(n) = 4n for all integers n ≥ 0.
The same function also can be defined recursively as follows:
F(n)=1, f(n + 1)=4f(n), for n > 0
To prove that the function is well defined we've to prove existence and the uniqueness of such function. during this case, existence is obvious as f(n) =4n.

Growth Functions

The growth of a function is usually described employing a special notation, O-notation. It provides a special thanks to comparing relation sizes of function that's very useful within the analysis of computer algorithms. It often happens that the time or memory space requirements for the algorithms available to try to do a particular job differ from one another on such a grand scale that differences of just a continuing the factor is completely overshadowed. The O-notation maker use of approximations that highlight these large-scale differences while ignoring differences of a continuing factor and differences that only occur for little sets of the input files.

Question2. Discuss direct and indirect proof techniques.

Answer. Proof Techniques - A a significant requirement for reading this subject is that the ability to follow proofs. In mathematical arguments, we employ the accepted rules of deduction, and lots of proofs are simply a sequence of such steps.

Direct Proof: Consider a group of hypotheses H1, H2, …., Hn from which we would like to inter a conclusion C.

Consider the example: Prove that if x and y are rational numbers then x + y is rational.

Solution: Since x and y are rational numbers. we will find integers p, q, m, n such x = p/q and y =m/n. Then x + Y =p/q + m/n=(pn + mq)/qn.

Since pn + mq and qn are both integers, we conclude that x + y may be a real number.

Indirect Proof: prove that isn't direct is called indirect. Two main sorts of indirect proof use both the negation and conclusion, in order that they are often suitable when that negation is straightforward to state. the primary sort of proof is contra-positive proof.

Quention3. Discuss Walks and Paths in Trees.

Answer. Walks and Paths

Definition - A the finite alternating sequence of vertices and edges beginning and ending with vertices such each edge is incident with the vertices preceding and following it's called a walk.
Vertices with which a walk begins and ends are called the terminal vertices of the given walk.
The remaining vertices within the walk are called intermediate vertices of the walk.
A walk is claimed to be a closed walk if the terminal points are the same.

Example

From the above definition, it's clear that no edge appears quite once during a walk.
Consider the graph given. we will observe that “v1av2bv3cv3d v4e v2f v5” is walk.

The sets of vertices and edges constituting a given enter a graph g forms a subgraph of G.A walk which isn't closed is named an open walk. within the above example, the walk “v1av2bv3cv1” may be a closed walk and therefore the walk “v1av2bv3dv4ev2fv5” is an open walk.

Definition

An open walk, during which no vertex appears more the once, is named a path or simple path.
(In other words, an open walk is claimed to be a path if it doesn't intersect itself. The number of edges during a path is named the length of the trail.

Question4. What's DFA? Discuss Transition System.

Answer. Deterministic Finite Automata (DFA)

The In the first sort of automata, we study intimately the finite accepters that are deterministic in their operation. We start with a particular formal definition of deterministic accepters.
Definition

A DFA is 5-tuple or quintuple M = (Q, , , q₀, F) where 
Q is a non-empty, finite set of states.
 is a non-empty, finite set of input alphabet.
 is transition function, which may be a mapping from Q ×  to Q. for this transition function the parameters to be passed are state and input symbol.
Based on the present state and input symbol, the machine may enter into another state.
q0  Q is that the start state.
F = Q is about accepting or final states.

Transition System (Transition graph)

A finite directed labeled graph during which each node or vertex of the graph represents a state and therefore the directed edges from one node to a different represent transition of a state. All the sides of the transition graph are labeled as input/output. for instance, a foothold labeled 1/0 specifies that for a particular state if the input is 1, then the output is 0.
Consider the subsequent diagram:

The initial state, q0 of the system is represented by a circle with an arrow pointing toward it.
the ultimate state, q1, is represented by two concentric circles.
The directed edges from the initial state to the ultimate state are labeled as input/output.

Question5. Differentiate between Moore machine and Mealy machine.

Answer. Moore and Mealy Machine
 
The automata systems we've discussed thus far are limited to binary output. That is, the system can either accept or reject a string. therein system, this acceptability is set supported the reachability of the initial state to the ultimate state. This property of the system produces restrictions in choosing output from another alphabet, then output. you'll remove this constraint using both the Moore and mealy machine, which help in generating output from a particular output alphabet.

Let us denote the output function with the symbol . Thus, when the output of an automat system is dependent only on this state, then Output=  (q (t)), where q(t) is that the present state.
The above automata system is named a Moore machine.

Alternatively, when the output of the automata system is trusted both this input and therefore the present state, then,
Output=(q(t)), x(t), where q(t) is that the present state and x(t) is that the present input.
The above automat system is named a mealy machine.

Since the output of a mealy machine depends on both the input and therefore the present state, no output is generated when the input may be a null string. this suggests that when the input is ^, the output is also ^. However, just in the case of the Moore machine, there's some output of the Moore machine only hooked into this state and not on this input. Hence, when the input to a Moore machine is ^, the output is (q0). 

Question6. Define context-free grammar. what's an ambiguous grammar? Explain with an example.

Answer. Context-free Grammars - A grammar G maybe a quadruple G = (VN, VT, , S), where VN is about of variables or non-terminals
VT is about of terminals symbols 
 is about of productions
S is that the start symbol,
Is said to be type 2 grammar or context-free grammar (CFG), if all the Productions are of the shape a → , where
 (VN VT)* and A VN. The symbol ^ (indicating NULL string) can appear on the proper hand side of any production.
The language generated from this grammar is named type-2 language or context-free language (CFL)
Observations:

there's only symbol A on the left side of the assembly which symbol must be a non-terminal.
 (VN VT)* implies that the right side of the string may contain any number of terminals and non-terminals including ^ (NULL string).

Every regular grammar may be a CFG and hence a daily language is additionally context-free language but the reverse isn't true string w.

Notation: nx(w) = number of x’s within the string w.

Ambiguous Grammar
 
Let G =(VN, VT, , S) be a context-free grammar. A grammar G is or more different derivation trees exist by applying either the leftmost derivation or rightmost derivation even through the derivation look different and if the structure of derivation trees obtained is the same, we cannot conclude that the grammar is ambiguous. it's not the multiplicity of the derivation that causes ambiguity. But it's the existence of two or more derivation trees for an equivalent string w derived from the basis labeled S.
Example
Verify whether or not the subsequent grammar is ambiguous.
S→As|a
A→aA|a

Solution: Consider the 2 leftmost derivations for the string aaaa.

S →aS
→aaS
→aaaS
→aaaA
→aaaa.

Other way: S→A

→aA
→aaA
→aaaA
→aaaa.

Since there are two leftmost derivation for an equivalent sentence aaaa. The given grammar is ambiguous.