Recent questions without an upvoted answer / GATE Overflow for GATE CSE

Let $L$={$ab,aa,baa$}.Which of the following strings are in $L^*$ :$abaabaaabaa$, $aaaabaaaa$, $baaaaabaaaab$, $baaaaabaa$? Which strings are in $L^4$?

Naveen Kumar 3

383 views

Naveen Kumar 3 asked Mar 17, 2019

1 votes

0 answers

9215

Peter Linz Edition 4 Exercise 1.2 Question 3 (Page No. 27)
Prove that $(w^R)^R=w$ for all $w∈Σ^*$.

Prove that $(w^R)^R=w$ for all $w∈Σ^*$.

Naveen Kumar 3

173 views

Naveen Kumar 3 asked Mar 17, 2019

1 votes

1 answer

9216

Peter Linz Edition 4 Exercise 1.2 Question 1 (Page No. 27)
Use induction on $n$ to show that $|u^n|=n|u|$ for all strings $u$ and all $n$.

Use induction on $n$ to show that $|u^n|=n|u|$ for all strings $u$ and all $n$.

Naveen Kumar 3

293 views

Naveen Kumar 3 asked Mar 17, 2019

0 votes

0 answers

9217

Peter Linz Edition 5 Exercise 11.3 Question 6 (Page No. 296)
Without explicitly constructing it, show that there exists a context-sensitive grammar for the language $L=\{www^R: w,u\in\{a,b\}^+,|w|\geq|u|\}$.

Without explicitly constructing it, show that there exists a context-sensitive grammar for the language $L=\{www^R: w,u\in\{a,b\}^+,|w|\geq|u|\}$.

Rishi yadav

263 views

Rishi yadav asked Mar 17, 2019

0 votes

0 answers

9218

Peter Linz Edition 5 Exercise 11.3 Question 5 (Page No. 296)
$\text{Theorem}:$ Every context-sensitive language $L$ is recursive. For $m$ in Theorem, give explicit bounds for $m$ as a function of $|w|$ and $|V\cup T|$.

$\text{Theorem}:$ Every context-sensitive language $L$ is recursive.For $m$ in Theorem, give explicit bounds for $m$ as a function of $|w|$ and $|V\cup T|$.

Rishi yadav

158 views

Rishi yadav asked Mar 17, 2019

0 votes

0 answers

9219

Peter Linz Edition 5 Exercise 11.3 Question 4 (Page No. 296)
Show that the family of context-sensitive languages is closed under reversal.

Show that the family of context-sensitive languages is closed under reversal.

Rishi yadav

135 views

Rishi yadav asked Mar 17, 2019

0 votes

0 answers

9220

Peter Linz Edition 5 Exercise 11.3 Question 3 (Page No. 296)
Show that the family of context-sensitive languages is closed under union.

Show that the family of context-sensitive languages is closed under union.

Rishi yadav

146 views

Rishi yadav asked Mar 17, 2019

0 votes

0 answers

9221

Peter Linz Edition 5 Exercise 11.3 Question 2 (Page No. 296)
Find context-sensitive grammars for the following languages. $(a)$ $L=\{w: n_a(w) = n_b(w) = n_c(w)\}$. $(b)$ $L=\{w: n_a(w) = n_b(w) < n_c(w)\}$.

Find context-sensitive grammars for the following languages.$(a)$ $L=\{w: n_a(w) = n_b(w) = n_c(w)\}$.$(b)$ $L=\{w: n_a(w) = n_b(w) < n_c(w)\}$.

Rishi yadav

163 views

Rishi yadav asked Mar 17, 2019

0 votes

0 answers

9222

Peter Linz Edition 5 Exercise 11.3 Question 1 (Page No. 296)
Find the context-sensitive grammars for the following languages. $\text{(a)}$ $L=\{a^{n+1}b^nc^{n-1} : n\geq 1\}$. $\text{(b)}$ $L=\{a^{n}b^nc^{2n} : n\geq 1\}$. $\text{(c)}$ $L=\{a^{n}b^mc^{n}d^m : n\geq 1, m\geq1\}$. $\text{(d)}$ $L=\{ww : w\in \{a,b\}^+\}$. $\text{(e)}$ $L=\{a^{n}b^nc^{n}d^m : n\geq 1\}$.

Find the context-sensitive grammars for the following languages.$\text{(a)}$ $L=\{a^{n+1}b^nc^{n-1} : n\geq 1\}$.$\text{(b)}$ $L=\{a^{n}b^nc^{2n} : n\geq 1\}$.$\text{(c)}...

Rishi yadav

168 views

Rishi yadav asked Mar 17, 2019

0 votes

0 answers

9223

Peter Linz Edition 5 Exercise 11.2 Question 9 (Page No. 290,291)
A grammar $G = (V, T, S, P)$ is called $\text{unrestricted }$ if all the production are of the form $u\rightarrow v$, where $u$ is nit $(V\cup T)^+$ and $v$ is int $(V\cup T)^*$ Some authors give ... the same as the one we use, in the sense that for every grammar of one type, there is an equivalent grammar of the other type.

A grammar $G = (V, T, S, P)$ is called $\text{unrestricted }$ if all the production are of the form ...

Rishi yadav

230 views

Rishi yadav asked Mar 17, 2019

0 votes

0 answers

9224

Peter Linz Edition 5 Exercise 11.2 Question 8 (Page No. 290)
Every unrestricted grammar there exists an equivalent unrestricted grammar, all of whose productions have the form $u\rightarrow v,$ with $u,v\in (V \cup T)^+$ and $|u| \leq |v|$, or $A\rightarrow\lambda$ with $A\in V$ Show that the conclusion still holds if we add the further conditions $|u|\leq2$ and $|v|\leq2$

Every unrestricted grammar there exists an equivalent unrestricted grammar, all of whose productions have the form ...

Rishi yadav

170 views

Rishi yadav asked Mar 17, 2019

0 votes

0 answers

9225

Peter Linz Edition 5 Exercise 11.2 Question 7 (Page No. 290)
Show that for every unrestricted grammar there exists an equivalent unrestricted grammar, all of whose productions have the form $u\rightarrow v,$ with $u,v\in (V \cup T)^+$ and $|u| \leq |v|$, or $A\rightarrow\lambda$ with $A\in V$

Show that for every unrestricted grammar there exists an equivalent unrestricted grammar, all of whose productions have the form ...

Rishi yadav

154 views

Rishi yadav asked Mar 17, 2019

1 votes

0 answers

9226

Peter Linz Edition 5 Exercise 11.2 Question 6 (Page No. 290)
$\text{Theorem}:$ For every recursively enumerable language $L$, there exists an unrestricted grammar $G$, such that $L=L(G)$. Construct a Turing machine for $L(01(01)^*)$, then find an unrestricted grammar for it using the construction in Theorem. Give a derivation for $0101$ using the resulting grammar.

$\text{Theorem}:$ For every recursively enumerable language $L$, there exists an unrestricted grammar $G$, such that $L=L(G)$.Construct a Turing machine for $L(01(01)^*)$...

Rishi yadav

190 views

Rishi yadav asked Mar 17, 2019

0 votes

0 answers

9227

Peter Linz Edition 5 Exercise 11.2 Question 5 (Page No. 290)
$\text{Theorem}:$ For every recursively enumerable language $L$, there exists an unrestricted grammar $G$, such that $L = L(G)$. Give the details of the proof of the Theorem.

$\text{Theorem}:$ For every recursively enumerable language $L$, there exists an unrestricted grammar $G$, such that $L = L(G)$.Give the details of the proof of the Theor...

Rishi yadav

247 views

Rishi yadav asked Mar 17, 2019

0 votes

0 answers

9228

Payment problem
While doing the payment online, I am getting the message “Please verify the data entered and try again”. This is happening in the stage when I am entering my application number and dob. I verified the application number and dob again and again. What else could have gone wrong? Please help.

While doing the payment online, I am getting the message “Please verify the data entered and try again”. This is happening in the stage when I am entering my applicat...

shraddha priya

1.5k views

shraddha priya asked Mar 17, 2019

0 votes

0 answers

9229

Peter Linz Edition 5 Exercise 11.2 Question 4 (Page No. 290)
Prove that constructed grammar cannot generate any sentence with $a\space b$ in it. $S\rightarrow S_1B,$ $S_1\rightarrow aS_1b,$ $bB\rightarrow bbbB,$ $aS_1b\rightarrow aa,$ $B\rightarrow \lambda$

Prove that constructed grammar cannot generate any sentence with $a\space b$ in it. $S\rightar...

Rishi yadav

148 views

Rishi yadav asked Mar 17, 2019

0 votes

0 answers

9230

Peter Linz Edition 5 Exercise 11.2 Question 3 (Page No. 290)
Consider a variation on grammars in which the starting point of any derivation can be a finite set of strings, rather than a single variable. Formalize this concept, then investigate how such grammars relate to the unrestricted grammars we have used here.

Consider a variation on grammars in which the starting point of any derivation can be a finite set of strings, rather than a single variable. Formalize this concept, then...

Rishi yadav

162 views

Rishi yadav asked Mar 17, 2019

0 votes

0 answers

9231

Peter Linz Edition 5 Exercise 11.2 Question 2 (Page No. 290)
What difficulties would arise if we allowed the empty string as the left side of a production in an unrestricted grammar$?$

What difficulties would arise if we allowed the empty string as the left side of a production in an unrestricted grammar$?$

Rishi yadav

169 views

Rishi yadav asked Mar 17, 2019

0 votes

0 answers

9232

Peter Linz Edition 5 Exercise 11.2 Question 1 (Page No. 290)
What language does the unrestricted grammar $S\rightarrow S_1B,$ $S_1\rightarrow aS_1b,$ $bB\rightarrow bbbB,$ $aS_1b\rightarrow aa,$ $B\rightarrow \lambda$ derive$?$

What language does the unrestricted grammar $S\rightarrow S_1B,$ ...

Rishi yadav

214 views

Rishi yadav asked Mar 17, 2019

0 votes

0 answers

9233

Application form editing
In the section 1 of Registration details, I have apparently entered my old phone number which is no longer valid. And when I am opting to edit, the page shows my application where all other sections are editable but not section 1. How do I update my number now? Please help.

In the section 1 of Registration details, I have apparently entered my old phone number which is no longer valid. And when I am opting to edit, the page shows my applicat...

shraddha priya

579 views

shraddha priya asked Mar 17, 2019

3 votes

0 answers

9234

Kenneth Rosen Edition 7 Exercise 2.2 Question 49 (Page No. 137)
Find ${\displaystyle \bigcup _{i=1}^{\infty }A_{i}} and \bigcup_{i=1}^{\infty} A_{i}$ if for every positive integer i, a) Ai = {i, i + 1, i + 2, . . .}. b) Ai = {0, i}. c) Ai = (0, i), that is, the set of real numbers x with 0 < x < i. d) Ai = (i,∞), that is, the set of real numbers x with x > i.

Find ${\displaystyle \bigcup _{i=1}^{\infty }A_{i}} and \bigcup_{i=1}^{\infty} A_{i}$ if for every positive integer i,a) Ai = {i, i + 1, i + 2, . . .}.b) Ai = {0, i}.c) A...

sumitr

551 views

sumitr asked Mar 17, 2019

0 votes

0 answers

9235

Foruzan,Error Detection and Correction: Exercise,Ques:23 Please Explain
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 ... 24 −1 − 4 = 11 (acceptable) Comment: The code is C(15, 11) with dmin = 3. How this n=15 came?? please explain

23: We need a dataword of at least 11 bits. Find the values of k and n in the Hammingcode C(n, k) with dmin :3. Soln: We need to find k = 2m −1 − m ≥ 11. We use tr...

Nishi Agarwal

5.2k views

Nishi Agarwal asked Mar 17, 2019

1 votes

0 answers

9236

Foruzan, Error Detection and Correction :Exercise Ques: 32 Please Explain
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.

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 th...

Nishi Agarwal

5.2k views

Nishi Agarwal asked Mar 17, 2019

0 votes

0 answers

9237

Gate Admission -IISc or IITB
Hello, Please comment your opinion on IITB or IISc, I know this depends on personal preference to some extent because both the institutes are awesome, but I would like to know points you are considering to take the decision

Hello,Please comment your opinion on IITB or IISc, I know this depends on personal preference to some extent because both the institutes are awesome, but I would like to ...

Ahabnnc

860 views

Ahabnnc asked Mar 17, 2019

0 votes

1 answer

9238

self doubt variable scope
#include <stdio.h> /* global variable declaration */ int g = 20; int main () { /* local variable declaration */ int g ; printf ("value of g = %d\n", g); return 0; } why this printing value of g is 0 instead of garbage because g is declared which is local variable in main function. are variables inside main function by default global?

#include <stdio.h /* global variable declaration */ int g = 20; int main () { /* local variable declaration */ int g ; printf ("value of g = %d\n", g); return 0; }why thi...

Ram Swaroop

420 views

Ram Swaroop asked Mar 17, 2019

0 votes

1 answer

9239

Self-doubt
How to improve cache hit rate in case of transfer of element from 2-D array to matrix.? (Consider the column major order in 2D array)

How to improve cache hit rate in case of transfer of element from 2-D array to matrix.? (Consider the column major order in 2D array)

Anuranjan

257 views

Anuranjan asked Mar 17, 2019

0 votes

0 answers

9240

Self doubt
Hello I am from electronics background. I got Gate score 744 and rank 464 in Gate computer science What are my options next?

Hello I am from electronics background. I got Gate score 744 and rank 464 in Gate computer scienceWhat are my options next?

Vipin Rai

481 views

Vipin Rai asked Mar 17, 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