Recent questions without answers

0 votes

0 answers

4291

Swap consecutive algorithm
There are n students standing in a line. The students have to rearrange themselves in ascending order of their roll numbers. This rearrangement must be accomplished only by successive swapping of adjacent students. (i) Design an algorithm for this purpose ... of swaps required. (ii) Derive an expression for the number of swaps needed by your algorithm in the worst case.

There are n students standing in a line. The students have to rearrange themselves in ascending order of their roll numbers. This rearrangement must be accomplished only ...

269 views

Priyanka17 asked Apr 18, 2019

0 votes

0 answers

4292

self doubt *0/1 knapsack problem*
In 0/1 knapsack problem ,suppose if maximum weight is given as W and we are asked to find out max profit then * IS IT NECESSARY THAT THE TOTAL WEIGHT SHOULD BE EXACTLY EQUAL TO W OR IT CAN BE LESS THAN W AS WELL????

In 0/1 knapsack problem ,suppose if maximum weight is given as W and we are asked to find out max profit then * IS IT NECESSARY THAT THE TOTAL WEIGHT SHOULD BE EXACTLY EQ...

691 views

karan25gupta asked Apr 17, 2019

0 votes

0 answers

4293

Peter Linz Edition 4 Exercise 6.1 Question 25 (Page No. 164)
Prove the following counterpart of Exercise 23. Let the set of productions involving the variable $A$ on the left be divided into two disjoint subsets $A\rightarrow x_1A|x_2A|...|x_nA,$ and, $A\rightarrow y_1|y_2|...|y_m,$ where $A$ is not a ... $Z\rightarrow x_i|Zx_i,$ $i=1,2,3, ,n.$ is equivalent to the original grammar.

Prove the following counterpart of Exercise 23. Let the set of productions involving the variable $A$ on the left be divided into two disjoint subsets ...

142 views

Naveen Kumar 3 asked Apr 17, 2019

0 votes

0 answers

4294

Peter Linz Edition 4 Exercise 6.1 Question 24 (Page No. 164)
Use the result of the preceding exercise to rewrite the grammar $A\rightarrow Aa|aBc|\lambda,$ $B\rightarrow Bb|bc$ so that it no longer has productions of the form $A → Ax$ or $B → Bx.$

Use the result of the preceding exercise to rewrite the grammar$A\rightarrow Aa|aBc|\lambda,$$B\rightarrow Bb|bc$so that it no longer has productions of the form $A → A...

193 views

Naveen Kumar 3 asked Apr 17, 2019

0 votes

0 answers

4295

Peter Linz Edition 4 Exercise 6.1 Question 23 (Page No. 163)
Prove the following result. Let $G = (V, T, S, P )$ be a context-free grammar. Divide the set of productions whose left sides are some given variable (say, $A$), into two disjoint subsets $A\rightarrow Ax_1|Ax_2|...|Ax_n,$ $A\rightarrow y_1|y_2|...|y_m,$ ... $Z\rightarrow x_i|x_iZ,$ $i=1,2,3, ,n.$ Then $L (G) = L ( \widehat G).$

Prove the following result. Let $G = (V, T, S, P )$ be a context-free grammar. Divide the set of productions whose left sides are some given variable (say, $A$), into two...

160 views

Naveen Kumar 3 asked Apr 17, 2019

0 votes

0 answers

4296

Peter Linz Edition 4 Exercise 6.1 Question 22 (Page No. 163)
A context-free grammar $G$ is said to be minimal for a given language $L$ if $complexity (G) ≤ complexity (\widehat G)$ for any $\widehat{G}$ generating $L$. Show by example that the removal of useless productions does not necessarily produce a minimal grammar.

A context-free grammar $G$ is said to be minimal for a given language $L$ if $complexity (G) ≤ complexity (\widehat G)$ for any $\widehat{G}$ generating $L$. Show by ex...

229 views

Naveen Kumar 3 asked Apr 17, 2019

0 votes

0 answers

4297

Peter Linz Edition 4 Exercise 6.1 Question 21 (Page No. 163)
It is possible to define the term simplification precisely by introducing the concept of complexity of a grammar. This can be done in many ways; one of them is through the length of all the strings giving the production rules ... the complexity in this sense. What can you say about the removal of $λ$-productions and unit-productions?

It is possible to define the term simplification precisely by introducing the concept of complexity of a grammar. This can be done in many ways; one of them is through th...

464 views

Naveen Kumar 3 asked Apr 17, 2019

0 votes

0 answers

4298

Peter Linz Edition 4 Exercise 6.1 Question 20 (Page No. 163)
Consider the procedure suggested in Theorem 6.2 for the removal of useless productions. Reverse the order of the two parts, first eliminating variables that cannot be reached from S, then removing those that do not yield a terminal string. Does the new procedure still work correctly? If so, prove it. If not, give a counterexample.

Consider the procedure suggested in Theorem 6.2 for the removal of useless productions. Reverse the order of the two parts, first eliminating variables that cannot be rea...

323 views

Naveen Kumar 3 asked Apr 17, 2019

0 votes

0 answers

4299

Peter Linz Edition 4 Exercise 6.1 Question 19 (Page No. 163)
Suppose that a context-free grammar $G = (V, T, S, P)$ has a production of the form $A → xy,$ where $x,y∈ (V\cup T)^+$. Prove that if this rule is replaced by $A\rightarrow By, B\rightarrow x,$ where $B ∉ V,$ then the resulting grammar is equivalent to the original one.

Suppose that a context-free grammar $G = (V, T, S, P)$ has a production of the form $A → xy,$ where $x,y∈ (V\cup T)^+$. Prove that if this rule is replaced by $A\righ...

157 views

Naveen Kumar 3 asked Apr 17, 2019

0 votes

0 answers

4300

Peter Linz Edition 4 Exercise 6.1 Question 18 (Page No. 162)
Justify the claim made in the proof of Theorem 6.1 that the variable $B$ can be replaced as soon as it appears.

Justify the claim made in the proof of Theorem 6.1 that the variable $B$ can be replaced as soon asit appears.

186 views

Naveen Kumar 3 asked Apr 17, 2019

1 votes

0 answers

4301

Peter Linz Edition 4 Exercise 6.1 Question 17 (Page No. 162)
Show that if a grammar has no $λ$-productions and no unit-productions, then the removal of useless productions by the construction of Theorem 6.2 does not introduce any such productions. Theorem 6.2 Let $G = (V, T, S, P )$ ... that does not contain any useless variables or productions.

Show that if a grammar has no $λ$-productions and no unit-productions, then the removal of useless productions by the construction of Theorem 6.2 does not introduce any ...

227 views

Naveen Kumar 3 asked Apr 17, 2019

0 votes

0 answers

4302

Peter Linz Edition 4 Exercise 6.1 Question 16 (Page No. 162)
Let $G$ be a grammar without $λ$-productions, but possibly with some unit-productions. Show that the construction of Theorem 6.4 does not then introduce any $λ$-productions. Theorem 6.4 Let $G = (V, T, S, P )$ be any context- ... $G$.

Let $G$ be a grammar without $λ$-productions, but possibly with some unit-productions. Show thatthe construction of Theorem 6.4 does not then introduce any $λ$-producti...

333 views

Naveen Kumar 3 asked Apr 17, 2019

1 votes

0 answers

4303

Peter Linz Edition 4 Exercise 6.1 Question 15 (Page No. 162)
Give an example of a situation in which the removal of $λ$-productions introduces previously nonexistent unit-productions.

Give an example of a situation in which the removal of $λ$-productions introduces previouslynonexistent unit-productions.

286 views

Naveen Kumar 3 asked Apr 17, 2019

0 votes

0 answers

4304

Branch Address
To get branch address, do we need base register value or Program Counter value?

To get branch address, do we need base register value or Program Counter value?

539 views

srestha asked Apr 17, 2019

0 votes

0 answers

4305

#DBMS#Transaction

308 views

Golam Murtuza asked Apr 17, 2019

0 votes

0 answers

4306

#Pipeliningdoubt
What is the concept of branch penalty , stall cycle and branch instructions and what are the formulas to get those ?? Someone please guide me..i am really facing much difficulty in these concepts while solving prev yr gate questions.

What is the concept of branch penalty , stall cycle and branch instructions and what are the formulas to get those ?? Someone please guide me..i am really facing much dif...

233 views

Ritabrata Dey asked Apr 16, 2019

0 votes

0 answers

4307

Peter Linz Edition 4 Exercise 6.1 Question 14 (Page No. 162)
Suppose that $G$ is a context-free grammar for which $λ ∈ L (G)$. Show that if we apply the construction in Theorem 6.3, we obtain a new grammar $\widehat{G}$ such that $L(\widehat{G} ) = L (G) –$ {$λ$}.

Suppose that $G$ is a context-free grammar for which $λ ∈ L (G)$. Show that if we apply theconstruction in Theorem 6.3, we obtain a new grammar $\widehat{G}$ such that...

197 views

Naveen Kumar 3 asked Apr 15, 2019

0 votes

0 answers

4308

Peter Linz Edition 4 Exercise 6.1 Question 11 (Page No. 162)
Complete the proof of Theorem 6.4. Theorem 6.4 Let $G = (V, T, S, P )$ be any context-free grammar without $λ$-productions. Then there exists a context-free grammar $\widehat{G}=(\widehat{V},\widehat{T},S,\widehat{P})$ that does not have any unit-productions and that is equivalent to $G$.

Complete the proof of Theorem 6.4.Theorem 6.4Let $G = (V, T, S, P )$ be any context-free grammar without $λ$-productions. Then there exists a context-free grammar $\wide...

279 views

Naveen Kumar 3 asked Apr 15, 2019

0 votes

0 answers

4309

Peter Linz Edition 4 Exercise 6.1 Question 10 (Page No. 162)
Complete the proof of Theorem 6.3. Theorem 6.3 Let $G$ be any context-free grammar with $λ$ not in $L (G)$. Then there exists an equivalent grammar $\widehat{G}$ having no $λ$-productions.

Complete the proof of Theorem 6.3.Theorem 6.3Let $G$ be any context-free grammar with $λ$ not in $L (G)$. Then there exists an equivalent grammar $\widehat{G}$having no ...

268 views

Naveen Kumar 3 asked Apr 15, 2019

0 votes

0 answers

4310

Peter Linz Edition 4 Exercise 6.1 Question 4 (Page No. 161)
In Theorem 6.1, why is it necessary to assume that $A$ and $B$ are different variables?

In Theorem 6.1, why is it necessary to assume that $A$ and $B$ are different variables?

287 views

Naveen Kumar 3 asked Apr 15, 2019

0 votes

0 answers

4311

Peter Linz Edition 4 Exercise 6.1 Question 3 (Page No. 161)
Show that the two grammars $S\rightarrow abAB|ba,$ $A\rightarrow aaa,$ $B\rightarrow aA|bb$ and $S\rightarrow abAaA|abAbb|ba,$ $A\rightarrow aaa$ are equivalent.

Show that the two grammars$S\rightarrow abAB|ba,$$A\rightarrow aaa,$$B\rightarrow aA|bb$ and$S\rightarrow abAaA|abAbb|ba,$$A\rightarrow aaa$ ...

187 views

Naveen Kumar 3 asked Apr 15, 2019

0 votes

0 answers

4312

Peter Linz Edition 4 Exercise 6.1 Question 2 (Page No. 161)
Show a derivation tree for the string $ababbac$, using grammar with productions $A\rightarrow a|aaA|abBC,$ $B\rightarrow abbA|b.$ also show the derivation tree for grammar with productions $A\rightarrow a|aaA|ababbAc|abbc,$ $B\rightarrow abbA|b.$

Show a derivation tree for the string $ababbac$, using grammar with productions$A\rightarrow a|aaA|abBC,$$B\rightarrow abbA|b.$also show the derivation tree for grammar w...

146 views

Naveen Kumar 3 asked Apr 15, 2019

0 votes

0 answers

4313

Peter Linz Edition 4 Exercise 6.1 Question 1 (Page No. 161)
Complete the proof of Theorem 6.1 by showing that $S\overset{*}{\Rightarrow}_{\widehat{G}} w$ implies $S\overset{*}{\Rightarrow}_{G} w$. Theorem 6.1 Let $G = (V, T, S, P)$ be a context-free grammar. Suppose that $P$ ... $P$, and adding to it $A\rightarrow x_1y_1x_2|x_1y_2x_2|...|x_1y_nx_2.$ Then, $L(\widehat{G})=L(G)$.

Complete the proof of Theorem 6.1 by showing that $S\overset{*}{\Rightarrow}_{\widehat{G}} w$implies $S\overset{*}{\Rightarrow}_{...

528 views

Naveen Kumar 3 asked Apr 15, 2019

0 votes

0 answers

4314

Peter Linz Edition 5 Exercise 8.1 Question 7(k) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free $L = \{a^nb^m: \text{n is prime and m is not prime}\}$.

Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free $L = \{a^nb^m: \text{n is prime and m is not ...

368 views

Rishi yadav asked Apr 15, 2019

0 votes

0 answers

4315

Peter Linz Edition 5 Exercise 8.1 Question 7(i) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free $L = \{a^nb^m: \text{n and m are both prime}\}$.

Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free $L = \{a^nb^m: \text{n and m are both prim...

196 views

Rishi yadav asked Apr 15, 2019

0 votes

0 answers

4316

Peter Linz Edition 5 Exercise 8.1 Question 7(h) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L = \{w\in\{a,b,c\}^*:n_a(w)+n_b(w)=2n_c(w),n_a(w) = n_b(w)\}$.

Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L = \{w\in\{a,b,c\}^*:n_a(w)+n_b(w)=2n_c(w),n_a(w) = n_b(w)\...

297 views

Rishi yadav asked Apr 15, 2019

0 votes

0 answers

4317

Peter Linz Edition 5 Exercise 8.1 Question 7(g) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L=\{w:n_a(w)/n_b(w) = n_c(w)\}$.

Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L=\{w:n_a(w)/n_b(w) = n_c(w...

179 views

Rishi yadav asked Apr 15, 2019

0 votes

0 answers

4318

Peter Linz Edition 5 Exercise 8.1 Question 7(f) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L = \{w:n_a(w) <n_b(w)<n_c(w)\}$.

Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $$L = \{w:n_a(w) <n_b(w)<n_c(w)\}$$.

224 views

Rishi yadav asked Apr 15, 2019

0 votes

0 answers

4319

Peter Linz Edition 5 Exercise 8.1 Question 7(e) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L= \{a^nb^jc^k:n<j,n\leq k \leq j\}$.

Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L= \{a^nb^jc^k:n<j,n\leq k \leq j\}$...

283 views

Rishi yadav asked Apr 15, 2019

0 votes

0 answers

4320

Peter Linz Edition 5 Exercise 8.1 Question 7(d) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L=\{a^nb^jc^k : k>n,k>j\}$.

Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L=\{a^nb^jc^k : k>n,k>j\}$.

195 views

Rishi yadav asked Apr 15, 2019

Page:

« prev
1
...
139
140
141
142
143
144
145
146
147
148
149
...
592
next »