Recent questions without answers / GATE Overflow for GATE CSE

Construct npda's that accept the following languages on $Σ =$ {$a, b, c$}.(a) $L =$ {$a^nb^{2n} : n ≥ 0$}.(b) $L =$ {$wcw^R : w ∈$ {$a, b$}$^*$}.(c) $L =$ {$a^nb^mc^...

Naveen Kumar 3

346 views

Naveen Kumar 3 asked Apr 20, 2019

1 votes

0 answers

4264

Peter Linz Edition 4 Exercise 7.1 Question 3 (Page No. 183)
Construct npda's that accept the following regular languages. (a) $L_1 = L (aaa^*b)$. (b) $L_1 = L (aab^*aba^*)$. (c & d here)

Construct npda's that accept the following regular languages.(a) $L_1 = L (aaa^*b)$.(b) $L_1 = L (aab^*aba^*)$.(c & d here)

Naveen Kumar 3

624 views

Naveen Kumar 3 asked Apr 20, 2019

0 votes

0 answers

4265

Peter Linz Edition 4 Exercise 7.1 Question 2 (Page No. 183)
Prove that an npda for accepting the language $L =$ { $ww^R : w ∈$ {$a, b$}$^+$ } does not accept any string not in {$ww^R$}.

Prove that an npda for accepting the language $L =$ { $ww^R : w ∈$ {$a, b$}$^+$ } does not accept any string not in {$ww^R$}.

Naveen Kumar 3

183 views

Naveen Kumar 3 asked Apr 20, 2019

1 votes

0 answers

4266

Peter Linz Edition 4 Exercise 7.1 Question 1 (Page No. 183)
Find a pda with fewer than four states that accepts the language $L=${$a^nb^n:n\geq 0$} $\cup$ {$a$}.

Find a pda with fewer than four states that accepts the language $L=${$a^nb^n:n\geq 0$} $\cup$ {$a$}.

Naveen Kumar 3

341 views

Naveen Kumar 3 asked Apr 20, 2019

0 votes

0 answers

4267

Bounded lattice
Can a countable infinite lattice be bounded?

Can a countable infinite lattice be bounded?

Manoj Kumar Pandey

593 views

Manoj Kumar Pandey asked Apr 20, 2019

0 votes

0 answers

4268

Probability of error detection
A block of bits with n rows and m columns uses horizontal and vertical parity bits for error detection. If exactly 4 bits are in error during transmission, derive an expression for the probability that the error will be detected.

A block of bits with n rows and m columns uses horizontal and vertical parity bits for error detection. If exactly 4 bits are in error during transmission, derive an expr...

Priyanka17

406 views

Priyanka17 asked Apr 20, 2019

1 votes

0 answers

4269

IITB direct TA admissions
When does IITb start with the offers of MTech round 1

When does IITb start with the offers of MTech round 1

Kartavya Kothari 1

510 views

Kartavya Kothari 1 asked Apr 19, 2019

0 votes

0 answers

4270

Peter Linz Edition 4 Exercise 6.3 Question 4 (Page No. 173)
Use the CYK method to determine if the string $w = aaabbbbab$ is in the language generated by the grammar $S → aSb|b$.

Use the CYK method to determine if the string $w = aaabbbbab$ is in the language generated by the grammar $S → aSb|b$.

Naveen Kumar 3

149 views

Naveen Kumar 3 asked Apr 19, 2019

0 votes

0 answers

4271

Peter Linz Edition 4 Exercise 6.3 Question 3 (Page No. 173)
Use the approach employed in Exercise 2 to show how the CYK membership algorithm can be made into a parsing method.

Use the approach employed in Exercise 2 to show how the CYK membership algorithm can be made into a parsing method.

Naveen Kumar 3

137 views

Naveen Kumar 3 asked Apr 19, 2019

0 votes

0 answers

4272

Peter Linz Edition 4 Exercise 6.3 Question 2 (Page No. 173)
Use the CYK algorithm to find a parsing of the string $aab$, using the grammar with productions $S\rightarrow AB,$ $A\rightarrow BB|a,$ $B\rightarrow AB|b.$

Use the CYK algorithm to find a parsing of the string $aab$, using the grammar with productions $S\rightarrow AB,$ $A\rightarrow BB|a,$ ...

Naveen Kumar 3

171 views

Naveen Kumar 3 asked Apr 19, 2019

0 votes

0 answers

4273

Peter Linz Edition 4 Exercise 6.3 Question 1 (Page No. 172)
Use the CYK algorithm to determine whether the strings $aabb, aabba,$ and $abbbb$ are in the language generated by the grammar with productions $S\rightarrow AB,$ $A\rightarrow BB|a,$ $B\rightarrow AB|b.$

Use the CYK algorithm to determine whether the strings $aabb, aabba,$ and $abbbb$ are in thelanguage generated by the grammar with productions $S\rightar...

Naveen Kumar 3

173 views

Naveen Kumar 3 asked Apr 19, 2019

0 votes

0 answers

4274

Peter Linz Edition 4 Exercise 6.2 Question 16 (Page No. 170)
“Two-standard form is general; for any context-free grammar $G$ with $λ ∉ L (G),$ there exists an equivalent grammar in two-standard form.” Prove this.

“Two-standard form is general; for any context-free grammar $G$ with $λ ∉ L (G),$ there exists an equivalent grammar in two-standard form.” Prove this.

Naveen Kumar 3

132 views

Naveen Kumar 3 asked Apr 19, 2019

0 votes

0 answers

4275

Peter Linz Edition 4 Exercise 6.2 Question 15 (Page No. 170)
A context-free grammar is said to be in two-standard form if all production rules satisfy the following pattern $A\rightarrow aBC,$ $A\rightarrow aB,$ $A\rightarrow a,$ where $A, B, C ∈ V$ and $a ∈ T$. Convert the grammar ... $S\rightarrow aSA,$ $A\rightarrow bABC,$ $B\rightarrow b,$ $C\rightarrow aBC$ into two-standard form.

A context-free grammar is said to be in two-standard form if all production rules satisfy the following pattern $A\rightarrow aBC,$ ...

Naveen Kumar 3

164 views

Naveen Kumar 3 asked Apr 19, 2019

0 votes

0 answers

4276

Peter Linz Edition 4 Exercise 6.2 Question 13 (Page No. 170)
Convert the grammar $S\rightarrow ABb|a,$ $A\rightarrow aaA|B,$ $B\rightarrow bAb$ into Greibach normal form.

Convert the grammar $S\rightarrow ABb|a,$ $A\rightarrow aaA|B,$ $B\rightarrow bAb$into Greibach normal form.

Naveen Kumar 3

236 views

Naveen Kumar 3 asked Apr 19, 2019

0 votes

0 answers

4277

Peter Linz Edition 4 Exercise 6.2 Question 12 (Page No. 170)
Convert the grammar $S\rightarrow ab|aS|aaS$ into Greibach normal form.

Convert the grammar $S\rightarrow ab|aS|aaS$ into Greibach normal form.

Naveen Kumar 3

175 views

Naveen Kumar 3 asked Apr 19, 2019

0 votes

0 answers

4278

Peter Linz Edition 4 Exercise 6.2 Question 11 (Page No. 170)
Convert the following grammar into Greibach normal form. $S\rightarrow aSb|ab$

Convert the following grammar into Greibach normal form. $S\rightarrow aSb|ab$

Naveen Kumar 3

210 views

Naveen Kumar 3 asked Apr 19, 2019

0 votes

0 answers

4279

Peter Linz Edition 4 Exercise 6.2 Question 10 (Page No. 170)
Convert the grammar $S\rightarrow aSb|bSa|a|b$ into Greibach normal form.

Convert the grammar $S\rightarrow aSb|bSa|a|b$ into Greibach normal form.

Naveen Kumar 3

198 views

Naveen Kumar 3 asked Apr 19, 2019

0 votes

0 answers

4280

Peter Linz Edition 4 Exercise 6.2 Question 9 (Page No. 170)
Show that for every context-free grammar $G = (V, T, S, P)$ there is an equivalent one in which all productions have the form $A → aBC,$ or $A → λ,$ where $a∈Σ$ $\cup$ {$\lambda$} , $A,B,C∈V$.

Show that for every context-free grammar $G = (V, T, S, P)$ there is an equivalent one in which all productions have the form $A → aBC,$or ...

Naveen Kumar 3

131 views

Naveen Kumar 3 asked Apr 19, 2019

0 votes

0 answers

4281

Peter Linz Edition 4 Exercise 6.2 Question 8 (Page No. 169)
A linear language is one for which there exists a linear grammar [A linear grammar is a grammar in which at most one variable can occur on the right side of any production, without restriction on the position of this variable. Clearly, a regular grammar is always ... $A\rightarrow a,$ where $a∈ T$ , $A, B∈ V,$ such that $L = L (G)$.

A linear language is one for which there exists a linear grammar[A linear grammar is a grammar in which at most one variable can occur on the right side of any production...

Naveen Kumar 3

192 views

Naveen Kumar 3 asked Apr 19, 2019

0 votes

0 answers

4282

Peter Linz Edition 4 Exercise 6.2 Question 7 (Page No. 169)
Draw the dependency graph for the grammar in Exercise 4.

Draw the dependency graph for the grammar in Exercise 4.

Naveen Kumar 3

296 views

Naveen Kumar 3 asked Apr 19, 2019

1 votes

0 answers

4283

Peter Linz Edition 4 Exercise 6.2 Question 6 (Page No. 169)
Let $G = (V, T, S, P)$ be any context-free grammar without any $λ$-productions or unit-productions. Let $k$ be the maximum number of symbols on the right of any production in $P$. Show that there is an equivalent grammar in Chomsky normal form with no more than $(k-1)|P|+|T|$ production rules.

Let $G = (V, T, S, P)$ be any context-free grammar without any $λ$-productions or unit-productions.Let $k$ be the maximum number of symbols on the right of any productio...

Naveen Kumar 3

1.1k views

Naveen Kumar 3 asked Apr 19, 2019

0 votes

0 answers

4284

Peter Linz Edition 4 Exercise 6.2 Question 5 (Page No. 169)
Convert the grammar with productions $S\rightarrow AB|aB,$ $A\rightarrow aab|\lambda,$ $B\rightarrow bbA$ into Chomsky normal form.

Convert the grammar with productions$S\rightarrow AB|aB,$$A\rightarrow aab|\lambda,$$B\rightarrow bbA$ into Chomsky normal form.

Naveen Kumar 3

281 views

Naveen Kumar 3 asked Apr 19, 2019

0 votes

0 answers

4285

Peter Linz Edition 4 Exercise 6.2 Question 4 (Page No. 169)
Transform the grammar with productions $S\rightarrow abAB,$ $A\rightarrow bAB|\lambda,$ $B\rightarrow BAa|A|\lambda$ into Chomsky normal form.

Transform the grammar with productions$S\rightarrow abAB,$$A\rightarrow bAB|\lambda,$$B\rightarrow BAa|A|\lambda$ into Chomsky normal form.

Naveen Kumar 3

240 views

Naveen Kumar 3 asked Apr 19, 2019

0 votes

0 answers

4286

Peter Linz Edition 4 Exercise 6.2 Question 3 (Page No. 169)
Transform the grammar $S\rightarrow aSaA|A, A\rightarrow abA|b$ into Chomsky normal form.

Transform the grammar $S\rightarrow aSaA|A, A\rightarrow abA|b$ into Chomsky normal form.

Naveen Kumar 3

174 views

Naveen Kumar 3 asked Apr 19, 2019

0 votes

0 answers

4287

Peter Linz Edition 4 Exercise 6.2 Question 2 (Page No. 169)
Convert the grammar $S\rightarrow aSb|ab$ into Chomsky normal form.

Convert the grammar $S\rightarrow aSb|ab$ into Chomsky normal form.

Naveen Kumar 3

125 views

Naveen Kumar 3 asked Apr 19, 2019

0 votes

0 answers

4288

Peter Linz Edition 4 Exercise 6.2 Question 1 (Page No. 169)
Provide the details of the proof of Theorem 6.6. Theorem 6.6 Any context-free grammar $G = (V, T, S, P)$ with $λ ∉ L (G)$ has an equivalent grammar $\widehat G=(\widehat V,\widehat T,S,\widehat P)$ in Chomsky normal form.

Provide the details of the proof of Theorem 6.6.Theorem 6.6Any context-free grammar $G = (V, T, S, P)$ with $λ ∉ L (G)$ has an equivalent grammar $\widehat G=(\widehat...

Naveen Kumar 3

163 views

Naveen Kumar 3 asked Apr 19, 2019

0 votes

0 answers

4289

Assignment 2.9 (b) page no. 28 from book Classic Data Structures Second Edition by Debasis Samanta
Obtain the indexing formula for lower-right and upper-left triangular matrices using row-major order and column-major order. Consider the cases of : square matrix of order n x n. non-square matrix of order m x n, m ≠ n. I need a solution with explanation thanks in advance.

Obtain the indexing formula for lower-right and upper-left triangular matrices using row-major order and column-major order. Consider the cases of :square matrix of order...

mahi.0409

744 views

mahi.0409 asked Apr 18, 2019

0 votes

0 answers

4290

ISI paper
A block of bits with n rows and m columns uses horizontal and vertical parity bits for error detection. If exactly 4 bits are in error during transmission, derive an expression for the probability that the error will be detected.

A block of bits with n rows and m columns uses horizontal and vertical parity bits for error detection. If exactly 4 bits are in error during transmission, derive an expr...

Priyanka17

232 views

Priyanka17 asked Apr 18, 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