Web Page

$$\small{\overset{{\large{\textbf{Mark Distribution in Previous GATE}}}}{\begin{array}{|c|c|c|c|c|c|c|c|}\hline \textbf{Year}&\textbf{2019}&\textbf{2018}&\textbf{2017-1}&\textbf{2017-2}&\textbf{2016-1}&\textbf{2016-2}&\textbf{Minimum}&\textbf{Average}&\textbf{Maximum} \\\hline\textbf{1 Mark Count}&1&3&2&3&2&3&1&2.3&3 \\\hline\textbf{2 Marks Count}&4&2&3&1&4&3&1&2.8&4 \\\hline\textbf{Total Marks}&9&7&8&5&10&9&\bf{5}&\bf{8}&\bf{10}\\\hline \end{array}}}$$

# Recent questions in Computer Networks

1
23: We need a dataword of at least 11 bits. Find the values of k and n in the Hamming code C(n, k) with dmin :3. Soln: We need to find k = 2m −1 − m ≥ 11. We use trial and error to find the right answer: a. Let m = 1 k = 2m −1 − m = 21 −1 − 1 = 0 (not acceptable) b ... = 4 k = 2m −1 − m = 24 −1 − 4 = 11 (acceptable) Comment: The code is C(15, 11) with dmin = 3. How this n=15 came?? please explain
2
32: A sender needs to send the four data items Ox3456, OxABCC, Ox02BC, and OxEEEE. Answer the following: a. Find the checksum at the sender site. b. Find the checksum at the receiver site if there is no error.
3
Let $L_1$ be recursive and $L_2$ recursively enumerable. Show that $L_2-L_1$ is necessarily recursively enumerable.
4
Prove that the complement of a context-free language must be recursive.
1 vote
5
Is the family of recursive languages closed under concatenation$?$
6
Show that the families of recursively enumerable and recursive languages are closed under reversal.
7
Show that the family of recursive languages is closed under union and intersection.
1 vote
8
Is the family of recursively enumerable languages closed under intersection$?$
9
Show that the family of recursively enumerable languages is closed under union.
10
Show that if a language is not recursively enumerable, its complement cannot be recursive.
11
Let $L$ be a context-free language. Show that then $L^+$ is recusively enumerable. Suggest an enumeration procedure for it.
12
Let $L$ be a finite language. Show that then $L^+$ is recusively enumerable. Suggest an enumeration procedure for $L^+$
13
Prove that the set of all languages that are not recursively enumerable is not countable.
14
Prove that the set of all real numbers is not countable.
15
Consider the language $L = \{www:w\in\{a, b\}^+\}$. Discuss the construction and efficiency of algorithms for accepting $L$ on $\text(a)$ a standard Turing machine, $\text(b)$ on a two-tape deterministic Turing machine, $\text(c)$ on a single-tape nondeterministic Turing machine, $\text(d)$ on a two-tape nondeterministic Turing machine.
16
Consider the language $L = \{ww:w\in\{a, b\}^+\}$. Discuss the construction and efficiency of algorithms for accepting $L$ on $\text(a)$ a standard Turing machine, $\text(b)$ on a two-tape deterministic Turing machine, $\text(c)$ on a single-tape nondeterministic Turing machine, $\text(d)$ on a two-tape nondeterministic Turing machine.
17
Let $G_1$ and $G_2$ be grammars with $G_1$ regular. Is the problem $L(G_1) = L(G_2)$ decidable when $\text(a)$ $G_2$ is unrestricted, $\text(b)$ when $G_2$ is context-free, $\text(c)$ when $G_2$ is regular$?$
$\text{Theorem}:$ There exist no algorithms for deciding whether any given context-free grammar is ambiguous. Show that if the language $L(G_A)\space \cap L(G_B)$ in Theorem is regular, then it must be empty. Use this to show that the problem $“L(G)$ is regular $”$ is undecidable for context-free $G$.
Show that for arbitrary context-free grammars $G_1$ and $G_2$, the problem $”L(G_1) \space\cap L(G_2)$ is context-free$”$ is undecidable.