Solution

L is the complement of language (a* U b*) as w is any string not in (a* U b*) means w belongs to complement of (a* U b*).

So we need to make DFA for (a* U b*) and then complement the DFA.

Solution

Solution

R1 generates all strings which contains at least two “a’s”. But R2 does not generate strings such as “aba” or “abba” which contain two “a’s”, hence r2 is not correct for language L.

Solution

Solution

Pumping lemma says that:

For any language L, there exists an integer p (p is the pumping length), such that for all x ∈ L with |x| ≥ p, there exists u,v, w ∈ Σ*, such that x = uvw, and

(1) |uv| ≤ p

(2) |v| ≥ 1

(3) for all i ≥ 0: uvi w ∈ L

By rule 3 we can observe that in L=bab*aa

u=ba v=b (as vi =b*) and w=aa

So the minimum string which can be broken into u,v &w with the three conditions is “babaa” , hence minimum pumping length will be 5.

If we assume string “baaa” which is having length 4 and also present in language “bab*aa” , this language cannot be broken into u,v and w with three conditions.

For example in string “baaa”

u=ba v= ∈ & w=aa , this division of string into u,v &w violates rule 2. Hence 4 cannot be correct answer.

Solution

Solution

A token is a pair consisting of a token name and an optional attribute value. A lexeme is a sequence of characters in the source program that matches the pattern for a token and is identified by the lexical analyzer as an instance of that token.

For example: int value=3; Lexeme is “value” and Token is <id,1>

Types of tokens

The different Token classes are as follows:

class1: One token per keyword . class2: Tokens for the operators. Class3: One token representing all identifiers class4: Tokens representing constants (e.g. numbers) Class 5: Tokens for punctuation symbols such as left and right parenthesis, comma, semicolon.

So semicolon is also a lexeme which matches with pattern token class 5.

Solution

The grammar is not LL(1) as two productions have same first symbol

S→ Xa | dc (as first(X)=d) so these two productions will cause conflict in LL(1) parsing table.

The grammar is LALR(1) but not SLR(1)

No state differs only from look ahead so this is CLR(1) as well as LALR(1).

Since grammar is CLR(1) hence this is unambiguous also.

Solution

R1←a

R2 ← b

R1 ← R1+R2 // (a+b)

R2←c

R3← d

R2 ← R2 - R3 //(c-d)

R3←e

R2←R3*R2 //e*(c-d)

R1←R1+R2 // (a+b)+ e*(c-d)

Hence it requires minimum 3 registers [R1, R2 & R3]

Solution

a b c d e f g is wrong. Because b,c,g are adjacent nodes of a hence after b, c there must be g.

Instead a b c g d e f is correct.

All other options are correct

Solution

Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering. Topological Sorting for a graph is not possible if the graph is not a DAG.

For example, a topological sorting of the following graph is “5 4 2 3 1 0”. There can be more than one topological sorting for a graph.

For example, another topological sorting of the following graph is “4 5 2 3 1 0”. The first vertex in topological sorting is always a vertex with in-degree as 0 (a vertex with no incoming edges).

Solution

The determinant of a matrix = product of eigen values

|A| = 1*2*5*9 = 90

The determinant of (A^-1)^T = 1/ A^T = 1/|A| = 1/90 = 0.011

Solution

Symmetric: A relation R on a set A is called symmetric if (b, a) ∈ R whenever (a, b) ∈ R, for all a, b ∈ A.

Symmetric because for every (a, b), we have a (b, a).

Antisymmetric: A relation R on a set A such that for all a, b ∈ A, if (a, b) ∈ R and (b, a) ∈ R, then a = b is called antisymmetric.

Not antisymmetric because we have both (2, 3) and (3s, 2).

Solution

Let R be the binary relation from A to B. Then the inverse of R can be defined by R−1 = {(b, a)|(a, b) ∈ R}

For R= {(2,3),(3,4),(4,1),(1,3),(3,2)}

Inverse will be R’ = { (3,2)(,(3,1),(1,4),(4,3),2,3) } .

Solution

Solution

Valid means it should hold true for each case, like a tautology.

Satisfiability means at least one case it should be true. (it can be tautology also, but not be a contradiction).

There is a case for which ~(p->q) is true. So its satisfiable but not valid

P v~q has truth values “ T, T, F, T its not equivalent to ¬(p → q)

Solution

Chess board has 8x8 blocks.

If external boundaries are excluded we have exactly 8 horizontal edges for 7 rows.

And 8 vertical edges for 7 columns . In total 7*8 + 7*8 = 112

Other way.

There are 9 horizontal and 9 vertical lines. A horizontal line has 8 edges, vertical line has 8 edges

Total 9*8 + 9*8 = 144

Excluding the external boundaries: we need to remove top and bottom horizontal and right and left vertical lines. I.e. 8+8 + 8 +8 = 32

144-32 = 112

Solution

Solution

paging or segmentation

Solution

Because of more internal fragmentation

Solution

File system identifier: It is also known as a magic number that uniquely identifies the file type.

Solution

Since C-SCAN is a modification SCAN algorithm, it maintains its basic nature of providing

high throughput. Further, it provides the low variance in response time as compared to SCAN algorithm as the pending jobs on the other side of the disk may get chance to be executed and centre cylinders are not favoured.

Solution

The otimal page replacement for the above reference gives 11 page fault out of 22 references. Therefore, page fault rate, p is 50%.

EMAT = (1-p)*(M) + p*(PFST) = 0.5*100 + 0.5*3000 = 1550ns.

Solution

Since the system is byte addressable minimum request a process can make is 1 byte. Hence, 1024-1=1023 bytes of internal fragmentation is possible in worst case.

Solution

(5-3)+(8-3)+(18-8)+(25-18)+(35-25)+(39-35) = 38tracks*1.5seeks/track =57

Solution

(C) False. Deadlock can result in starvation, but starvation can happen without deadlock.

Solution

We can get the recurrence relation is T(n)=4T(n/2)+n

Apply masters theorem

a=4, b=2, k=1 and p=0

Case-1: a>b^k

=O(n^2)

Solution

Solution

Solution

Let A be the array containing n numbers.

Step 1: Sort array A.

Step 2: Traverse through A to find the most frequent element by keeping counters. Since the numbers with the same value would appear in consecutive locations in the sorted array A, this can be achieved in one pass. Let maximum frequency is MAX.

Step 3: Traverse through A once more to report all the elements that match whose frequencies match with MAX.

→ Since Step 1 needs O(nlogn) time, the overall time complexity is O(nlogn).

Solution

Solution

P: False. Some priority constraints may be unspecified, and multiple orderings may be possible for a given DAG. For example a graph G = (V,E) = ({a,b,c},{(a,b),(a,c)}) has valid topological orderings [a,b,c] or [a,c,b]. As another example,G = (V,E) = ({a,b},{}) has valid topological orderings [a,b] or [b,c].

Q:True. Both algorithms are guaranteed to produce the same shortest path weight, but if there are multiple shortest paths, Dijkstra’s will choose the shortest path according to the greedy strategy, and Bellman-Ford will choose the shortest path depending on the order of relaxations, and the two shortest path trees may be different.

R:False. It always terminates after |E| relaxations and |V| + |E| priority queue operations, but may produce incorrect results.

S:True. Both parts of the statement hold if and only if the graph is acyclic.

Solution

The following program will help you to understand the concept:#include<stdio.h>

void main()

{

char c='5';

int a=3,b=2;

printf("c=%d c=%c\n", c,c);

printf("a=%d a=%c\n",a,a);

printf("b=%d b=%c\n",b,b);

printf("%d\n%c\n", a+b+c, a+b+c);}

O/P:

c=53 c=5

a=3 a=

b=2 b=

58 //a+b+c in ASCII value,

: // character corresponding to 58

As far as C is concerned, a character is its numeric value. In fact, character literals in C, like 'a', have type int rather than type char.

Note that the char type is a type of it's own: the smallest possible integer type, usually 1 byte wide. So it is not only used for storing ASCII letters, it is also commonly used when working with small numbers 0-255 (unsigned) or -128 to 127 (signed), to save memory.