Answers by abhishekmehta4u / GATE Overflow for GATE CSE

2 votes

201

Peter Linz Edition 4 Exercise 1.2 Question 23 (Page No. 30)
Show that the grammars $S \rightarrow aSb|bSa|SS|a$ and $S \rightarrow aSb|bSa|a$ are not equivalent.

Show that the grammars $S \rightarrow aSb|bSa|SS|a$and $S \rightarrow aSb|bSa|a$are not equivalent.

300 views

answered Mar 19, 2019

0 votes

202

Galvin Edition 9 Exercise 3 Question 8 (Page No. 151)
Describe the differences among short-term, medium-term, and long term scheduling.

Describe the differences among short-term, medium-term, and long term scheduling.

467 views

answered Mar 19, 2019

1 votes

203

Galvin Edition 9 Exercise 3 Question 2 (Page No. 149-150)
Including the initial parent process, how many processes are created by the following program. #include <stdio.h> #include <unistd.h> int main() { fork(); fork(); fork(); return 0; }

Including the initial parent process, how many processes are created by the following program.#include <stdio.h>#include <unistd.h>int main(){fork(); fork(); ...

448 views

answered Mar 19, 2019

1 votes

204

Andrew S. Tanenbaum Edition 5th Exercise 8 Question 17 (Page No. 873)
Using the RSA public key cryptosystem, with a = 1, b = 2 . . . y = 25, z = 26. (a) If p = 5 and q = 13, list five legal values for d. (b) If p = 5, q = 31, and d = 37, find e. (c) Using p = 3, q = 11, and d = 9, find e and encrypt ‘‘hello’’.

Using the RSA public key cryptosystem, with a = 1, b = 2 . . . y = 25, z = 26.(a) If p = 5 and q = 13, list five legal values for d.(b) If p = 5, q = 31, and d = 37, find...

2.3k views

answered Mar 19, 2019

1 votes

205

Self doubt
O(n-1)+O(n)=O(n) O(n/2)+O(n)=O(n) but O(1)+O(2)+O(3)+...+O(n)=O(n(n+1)/2)=O(n^2) why?

O(n-1)+O(n)=O(n)O(n/2)+O(n)=O(n)but O(1)+O(2)+O(3)+...+O(n)=O(n(n+1)/2)=O(n^2)why?

492 views

answered Mar 19, 2019

0 votes

206

Kenneth Rosen Edition 7 Exercise 1.5 Question 26 (Page No. 66)
Let $Q(x, y)$ be the statement “ $x+y=x−y.$ ” If the domain for both variables consists of all integers, what are the truth values? $Q (1,1)$ $Q(2,0)$ $\forall y Q(1,y)$ $\exists x Q(x,2)$ $\exists x \exists y Q(x,y)$ $\forall x \exists y Q(x,y)$ $\exists x \forall y Q(x,y)$ $\forall y \exists x Q(x,y)$ $\forall x \forall y Q(x,y)$

Let $Q(x, y)$ be the statement “ $x+y=x−y.$ ” If the domain for both variables consists of all integers, what are the truth values?$Q (1,1)$$Q(2,0)$$\forall y Q(1,y...

606 views

answered Mar 19, 2019

2 votes

207

Ullman Exercise
What language is generated by the following grammer? S→ a | S+S | SS | S* | (S)

What language is generated by the following grammer?S→ a | S+S | SS | S* | (S)

457 views

answered Mar 19, 2019

2 votes

208

Self Doubt
How addition of $+3$ and $-3$ in sign magnitude form is $-5?$

How addition of $+3$ and $-3$ in sign magnitude form is $-5?$

633 views

answered Mar 19, 2019

3 votes

209

Kenneth Rosen Edition 7 Exercise 1.4 Question 52 (Page No. 56)
As mentioned in the text, the notation$\exists \sim xP (x)$ denotes “There exists a unique $x$ such that $P(x)$ is true.”If the domain consists of all integers, what are the truth values of these statements? $\exists \sim x(x>1)$ $\exists \sim x (x^2 = 1)$ $\exists x (x+3 = 2x)$ $\exists \sim x(x = x+1)$

As mentioned in the text, the notation$\exists \sim xP (x)$ denotes “There exists a unique $x$ such that $P(x)$ is true.”If the domain consists of all integers, what ...

565 views

answered Mar 18, 2019

1 votes

210

Peter Linz Edition 4 Exercise 1.2 Question 5 (Page No. 28)
Let $Σ = ${$a, b$} and $L = ${$aa, bb$}. Use set notation to describe $L^c$.

Let $Σ = ${$a, b$} and $L = ${$aa, bb$}. Use set notation to describe $L^c$.

789 views

answered Mar 18, 2019

0 votes

211

Peter Linz Edition 4 Exercise 1.2 Question 6 (Page No. 28)
Let $L$ be any language on a non-empty alphabet. Show that $L$ and $L^c$ cannot both be finite.

Let $L$ be any language on a non-empty alphabet. Show that $L$ and $L^c$ cannot both be finite.

514 views

answered Mar 18, 2019

2 votes

212

Kenneth Rosen Edition 7 Exercise 1.4 Question 45 (Page No. 56)
Show that $\exists x (P(x) \vee Q(x))$ and $\exists x P(x) \vee \exists x Q(x)$ are logically equivalent.

Show that $\exists x (P(x) \vee Q(x))$ and $\exists x P(x) \vee \exists x Q(x)$ are logically equivalent.

320 views

answered Mar 18, 2019

4 votes

213

Kenneth Rosen Edition 7 Exercise 1.4 Question 43 (Page No. 56)
Determine whether $\forall x (P(x) \rightarrow Q(x))$ and $\forall x P(x) \rightarrow \forall xQ(x)$ are logically equivalent . Justify your answer.

Determine whether $\forall x (P(x) \rightarrow Q(x))$ and $\forall x P(x) \rightarrow \forall xQ(x)$ are logically equivalent . Justify your answer.

996 views

answered Mar 18, 2019

1 votes

214

Kenneth Rosen Edition 7 Exercise 1.4 Question 11 (Page No. 53)
Let $P(x)$ be the statement “$x = x^2$”. If the domain consists of the integers, what are these truth values? $P(0)$ $P(1)$ $P(2)$ $P(-1)$ $\exists xP(x)$ $\forall x P(x)$

Let $P(x)$ be the statement “$x = x^2$”. If the domain consists of the integers, what are these truth values?$P(0)$$P(1)$$P(2)$$P(-1)$$\exists xP(x)$$\forall x P(x)$

2.5k views

answered Mar 18, 2019

1 votes

215

Peter Linz Edition 5 Exercise 11.1 Question 7 (Page No. 284)
Is the family of recursively enumerable languages closed under intersection$?$

Is the family of recursively enumerable languages closed under intersection$?$

213 views

answered Mar 17, 2019

1 votes

216

Peter Linz Edition 5 Exercise 11.1 Question 10 (Page No. 284)
Is the family of recursive languages closed under concatenation$?$

Is the family of recursive languages closed under concatenation$?$

321 views

answered Mar 17, 2019

2 votes

217

Self doubt
I have a confusion regarding the array implementation of binary tree ,i.e what are the index locations of the left child of a node whether it is 2i+1 or 2i and same for right child ,can anyone explain?

I have a confusion regarding the array implementation of binary tree ,i.e what are the index locations of the left child of a node whether it is 2i+1 or 2i and same for r...

852 views

answered Mar 17, 2019

1 votes

218

Peter Linz Edition 5 Exercise 11.1 Question 14 (Page No. 284)
If $L$ is recursive, is it necessarily true that $L^+$ is also recursive$?$

If $L$ is recursive, is it necessarily true that $L^+$ is also recursive$?$

162 views

answered Mar 17, 2019

8 votes

219

GATE CSE 2019 | Question: 1
A certain processor uses a fully associative cache of size $16$ kB, The cache block size is $16$ bytes. Assume that the main memory is byte addressable and uses a $32$-bit address. How many bits are required for the Tag and the Index fields respectively in the addresses ... $0$ bits $28$ bits and $4$ bits $24$ bits and $4$ bits $28$ bits and $0$ bits

A certain processor uses a fully associative cache of size $16$ kB, The cache block size is $16$ bytes. Assume that the main memory is byte addressable and uses a $32$-bi...

18.0k views

answered Mar 17, 2019

2 votes

220

Left recursion
In this question should we eliminate left recursion by putting values of S and A in the respective productions so answer will be c but if according to the given production than answer will be a how to solve?

In this question should we eliminate left recursion by putting values of S and A in the respective productions so answer will be c but if according to the given productio...

1.7k views

answered Mar 17, 2019

2 votes

221

Peter Linz Edition 5 Exercise 11.1 Question 19 (Page No. 284)
Show that the set of all irrational numbers is not countable.

Show that the set of all irrational numbers is not countable.

839 views

answered Mar 17, 2019

1 votes

222

Peter Linz Edition 5 Exercise 11.1 Question 15 (Page No. 284)
$\text{Theorem}:$ There exists a recursively enumerable language whose complement is not recursively enumerable. Choose a particular encoding for Turing machines, and with it, find one element of the languages $\bar{L}$ in Theorem

$\text{Theorem}:$ There exists a recursively enumerable language whose complement is not recursively enumerable.Choose a particular encoding for Turing machines, and with...

329 views

answered Mar 17, 2019

0 votes

223

Peter Linz Edition 5 Exercise 11.1 Question 12 (Page No. 284)
Let $L_1$ be recursive and $L_2$ recursively enumerable. Show that $L_2-L_1$ is necessarily recursively enumerable.

Let $L_1$ be recursive and $L_2$ recursively enumerable. Show that $L_2-L_1$ is necessarily recursively enumerable.

324 views

answered Mar 17, 2019

0 votes

224

Peter Linz Edition 5 Exercise 11.1 Question 11 (Page No. 284)
Prove that the complement of a context-free language must be recursive.

Prove that the complement of a context-free language must be recursive.

287 views

answered Mar 17, 2019

1 votes

225

Kenneth Rosen Edition 7 Exercise 1.3 Question 49 (Page No. 36)
Show that $p\downarrow q$ is logically equivalent to $\sim(p \vee q).$

Show that $p\downarrow q$ is logically equivalent to $\sim(p \vee q).$

589 views

answered Mar 16, 2019

1 votes

226

Kenneth Rosen Edition 7 Exercise 1.3 Question 23 (Page No. 35)
Show that $(p \rightarrow r) \wedge (q \rightarrow r)$ and $(p \vee q) \rightarrow r$ are logically equivalent.

Show that $(p \rightarrow r) \wedge (q \rightarrow r)$ and $(p \vee q) \rightarrow r$ are logically equivalent.

392 views

answered Mar 16, 2019

0 votes

227

Kenneth Rosen Edition 7 Exercise 1.3 Question 16 (Page No. 35)
Show that $p\leftrightarrow q$ and $(p \wedge q) \vee (\sim p \wedge \sim q)$ are logically equivalent.

Show that $p\leftrightarrow q$ and $(p \wedge q) \vee (\sim p \wedge \sim q)$ are logically equivalent.

833 views

answered Mar 16, 2019

0 votes

228

Kenneth Rosen Edition 7 Exercise 1.3 Question 15 (Page No. 34)
Determine whether $(\sim q \wedge (p \rightarrow q)) \rightarrow \sim p$ is a tautology.

Determine whether $(\sim q \wedge (p \rightarrow q)) \rightarrow \sim p$ is a tautology.

884 views

answered Mar 16, 2019

0 votes

229

Kenneth Rosen Edition 7 Exercise 1.3 Question 25 (Page No. 35)
Show that $(p \rightarrow r) \vee (q \rightarrow r)$ and $(p \wedge q) \rightarrow r$ are logically equivalent.

Show that $(p \rightarrow r) \vee (q \rightarrow r)$ and $(p \wedge q) \rightarrow r$ are logically equivalent.

411 views

answered Mar 16, 2019

0 votes

230

Kenneth Rosen Edition 7 Exercise 1.3 Question 26 (Page No. 35)
Show that $\sim p \rightarrow(q \rightarrow r)$ and $q \rightarrow(p \vee r)$ are logically equivalent.

Show that $\sim p \rightarrow(q \rightarrow r)$ and $q \rightarrow(p \vee r)$ are logically equivalent.

509 views

answered Mar 16, 2019

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true