Recent questions without answers / GATE Overflow for GATE CSE

0 votes

0 answers

4411

Ullman (TOC) Edition 3 Exercise 7.3 Question 4 (Page No. 297 - 298)
The $\text{shuffle}$ of two strings $w$ and $x$ is the set of all strings that one can get by interleaving the positions of $w$ and $x$ in any way. More precisely $,\text{shuffle(w,x)}$ is the set of strings $z$ such that Each position ... and $L_{2}$ are both $CFL's,$ then $\text{shuffle($L_{1},L_{2}$)}$ need not be a $CFL.$

The $\text{shuffle}$ of two strings $w$ and $x$ is the set of all strings that one can get by interleaving the positions of $w$ and $x$ in any way. More precisely $,\tex...

admin

179 views

admin asked Apr 11, 2019

0 votes

0 answers

4412

Ullman (TOC) Edition 3 Exercise 7.3 Question 3 (Page No. 297)
Show that the $CFL's$ are not closed under the following operations$:$ $\text{min}$ $\text{max}$ $\text{half}$ $\text{alt}$

Show that the $CFL's$ are not closed under the following operations$:$$\text{min}$$\text{max}$$\text{half}$$\text{alt}$

admin

124 views

admin asked Apr 11, 2019

0 votes

0 answers

4413

Ullman (TOC) Edition 3 Exercise 7.3 Question 2 (Page No. 297)
Consider the following languages$:$ $L_{1}=\{a^{n}b^{2n}c^{m}|n,m\geq 0\}$ $L_{2}=\{a^{n}b^{m}c^{2m}|n,m\geq 0\}$ Show that each of these languages is context-free by giving grammars for each. Is $L_{1}\cap L_{2}$ a $CFL?$ Justify your answer.

Consider the following languages$:$$L_{1}=\{a^{n}b^{2n}c^{m}|n,m\geq 0\}$$L_{2}=\{a^{n}b^{m}c^{2m}|n,m\geq 0\}$Show that each of these languages is context-free by giving...

admin

107 views

admin asked Apr 11, 2019

0 votes

0 answers

4414

Ullman (TOC) Edition 3 Exercise 7.3 Question 1 (Page No. 297)
Show that the $CFL's$ are closed under the following$:$ $\text{init},$ Hint$:$ Start with a $CNF$ grammar for the language $L.$ $\text{The operation $L/a,$}$ Hint$:$ Again,start with a $CNF$ grammar for $L.$ $\text{cycle, }$ Hint$:$ Try a $PDA-$based constrction.

Show that the $CFL's$ are closed under the following$:$$\text{init},$ Hint$:$ Start with a $CNF$ grammar for the language $L.$$\text{The operation $L/a,$}$ Hint$:$ Again...

admin

114 views

admin asked Apr 11, 2019

0 votes

0 answers

4415

Ullman (TOC) Edition 3 Exercise 7.2 Question 5 (Page No. 287)
Use Ogden's lemma $($Question $3)$ to show that the following languages are not $CFL's:$ $\{0^{i}1^{j}0^{k}|k=max(i,k)\}.$ $\{a^{n}b^{n}c^{i}|i\neq n\}.$ Hint$:$ If $n$ is the constant for Ogden's lemma,consider the stirng $z=a^{n}b^{n}c^{n+n!}.$

Use Ogden's lemma $($Question $3)$ to show that the following languages are not $CFL's:$$\{0^{i}1^{j}0^{k}|k=max(i,k)\}.$$\{a^{n}b^{n}c^{i}|i\neq n\}.$ Hint$:$ If $n$ is ...

admin

108 views

admin asked Apr 11, 2019

1 votes

0 answers

4416

Ullman (TOC) Edition 3 Exercise 7.2 Question 4 (Page No. 287)
Use Ogden's lemma $($Question $2)$ to simplify the proof in example $7.21$ that $L=\{\text{ww|w is in $\{0,1\}^{*}$}\}$ is not a $CFL.$Hint$:$With $z=0^{n}1^{n}0^{n}1^{n},$ make the two middle blocks distinguished.

Use Ogden's lemma $($Question $2)$ to simplify the proof in example $7.21$ that $L=\{\text{ww|w is in $\{0,1\}^{*}$}\}$ is not a $CFL.$Hint$:$With $z=0^{n}1^{n}0^{n}1^{n}...

admin

109 views

admin asked Apr 11, 2019

0 votes

0 answers

4417

Ullman (TOC) Edition 3 Exercise 7.2 Question 3 (Page No. 286)
There is a stronger version of the $CFL$ pumping lemma known as Ogden's lemma.It differs from the pumping lemma we proved by allowing us to focus on any $n$ $"$distinguished$"$ positions of a string $z$ and ... non-distinguished positions of $z$ are not present as we select a long path in the parse tree for $z.$

There is a stronger version of the $CFL$ pumping lemma known as Ogden's lemma.It differs from the pumping lemma we proved by allowing us to focus on any $n$ $"$distinguis...

admin

158 views

admin asked Apr 11, 2019

0 votes

0 answers

4418

Ullman (TOC) Edition 3 Exercise 7.2 Question 2 (Page No. 286)
When we try to apply the pumping lemma to a $CFL,$ the $"$adversary wins$"$ and we cannot complete the proof$.$Show what goes wrong when we choose $L$ to be one of the followinges$:$ $\{00,11\}.$ $\{0^{n}1^{n}|n\geq 1\}.$ $\text{The set of palindromes over alphabet \{0,1\}}.$

When we try to apply the pumping lemma to a $CFL,$ the $"$adversary wins$"$ and we cannot complete the proof$.$Show what goes wrong when we choose $L$ to be one of the fo...

admin

82 views

admin asked Apr 11, 2019

0 votes

0 answers

4419

Ullman (TOC) Edition 3 Exercise 7.2 Question 1 (Page No. 286)
Use the $CFL$ pumping lemma to show each of these languages not to be context-free$:$ $\left\{a^{i}b^{j}c^{k}|i<j<k\right\}.$ $\left\{a^{n}b^{n}c^{i}|i\leq n\right\}.$ ... the set of strings consisting of some string $w$ followed by the same string in reverse, and then the string $w$ again ,such as $001100001.$

Use the $CFL$ pumping lemma to show each of these languages not to be context-free$:$$\left\{a^{i}b^{j}c^{k}|i<j<k\right\}.$$\left\{a^{n}b^{n}c^{i}|i\leq n\right\}.$$\lef...

admin

124 views

admin asked Apr 11, 2019

0 votes

0 answers

4420

Ullman (TOC) Edition 3 Exercise 7.1 Question 12 (Page No. 279)
Use the construction of question $11$ to convert the grammar $S\rightarrow AA|0$ $A\rightarrow SS|1$ to $GNF.$

Use the construction of question $11$ to convert the grammar$S\rightarrow AA|0$$A\rightarrow SS|1$to $GNF.$

admin

125 views

admin asked Apr 11, 2019

0 votes

0 answers

4421

Ullman (TOC) Edition 3 Exercise 7.1 Question 11 (Page No. 278 - 279)
In this exercise, we shall show that for every context-free language $L$ containing at least one string other than $\in,$there is a $CFG$ in Greibach normal form that generates $L-\in.$ Recall that a Greibach normal form $(GNF)$ grammar is ... $(a).$ Then fi x the $B_{i}$ productions in any order , again $(a).$

In this exercise, we shall show that for every context-free language $L$ containing at least one string other than $\in,$there is a $CFG$ in Greibach normal form that gen...

admin

298 views

admin asked Apr 11, 2019

0 votes

0 answers

4422

Ullman (TOC) Edition 3 Exercise 7.1 Question 10 (Page No. 278)
Is it possible to find, for every context-free language without $\in,$ a grammar such that all its productions are either of the form $A\rightarrow BCD$ $($i.e., a body consisting of three variables$),$ or $A\rightarrow a$ $($i.e., a body consisting of a single terminal$)?$ Give either a proof or a counterexample.

Is it possible to find, for every context-free language without $\in,$ a grammar such that all its productions are either of the form $A\rightarrow BCD$ $($i.e., a body ...

admin

236 views

admin asked Apr 11, 2019

0 votes

0 answers

4423

Ullman (TOC) Edition 3 Exercise 7.1 Question 9 (Page No. 278)
Provide the inductive proofs needed to complete the following theorems$:$ The part of Theorem $7.4$ where we show that discovered symbols really are generating. Both directions of Theorem $7.6$ where we show the correctness of ... reachable symbols. The part of Theorem $7.11$ where we show that all pairs discovered really are unit pairs.

Provide the inductive proofs needed to complete the following theorems$:$ The part of Theorem $7.4$ where we show that discovered symbols really are generating.Both direc...

admin

316 views

admin asked Apr 11, 2019

0 votes

0 answers

4424

Ullman (TOC) Edition 3 Exercise 7.1 Question 8 (Page No. 278)
Let $G$ be an $\in-$production-free grammar whose total length of production bodies is $n.$ We convert $G$ to $CNF.$ Show that the CNF grammar has at most $O(n^{2})$ productions. Show that it is ... $n^{2}.$ Hint$:$Consider the construction that eliminates unit productions.

Let $G$ be an $\in-$production-free grammar whose total length of production bodies is $n.$ We convert $G$ to $CNF.$Show that the CNF grammar has at most $O(n^{2})$ produ...

admin

364 views

admin asked Apr 11, 2019

0 votes

0 answers

4425

Ullman (TOC) Edition 3 Exercise 7.1 Question 7 (Page No. 278)
Suppose $G$ is a CFG with $p$ productions, and no production body longer than $n.$Show that if $A\xrightarrow[G]{*}\in,$ then there is a derivation of $\in$ from $A$ of no more than $\frac{(n^{p}-1)}{(n-1)}$ steps. How close can you actually come to this bound$?$

Suppose $G$ is a CFG with $p$ productions, and no production body longer than $n.$Show that if $A\xrightarrow[G]{*}\in,$ then there is a derivation of $\in$ from $A$ of n...

admin

277 views

admin asked Apr 11, 2019

0 votes

0 answers

4426

Ullman (TOC) Edition 3 Exercise 7.1 Question 6 (Page No. 278)
Design a CNF grammar for the set of strings of balanced parentheses.You need not start from any particular non-CNF grammar.

Design a CNF grammar for the set of strings of balanced parentheses.You need not start from any particular non-CNF grammar.

admin

262 views

admin asked Apr 11, 2019

0 votes

0 answers

4427

Ullman (TOC) Edition 3 Exercise 7.1 Question 5 (Page No. 277 - 278)
Begin with the grammar$:$ $S\rightarrow aAa|bBb|\in$ $A\rightarrow C|a$ $B\rightarrow C|b$ $C\rightarrow CDE|\in$ $D\rightarrow A|B|ab$ Eliminate $\in-$productions. Eliminate any unit productions in the resulting grammar. Eliminate any useless symbols in the resulting grammar. Put the resulting grammar into Chomsky Normal Form.

admin

252 views

admin asked Apr 11, 2019

0 votes

0 answers

4428

Admission query for Placement opportunities
My gate score is 600 OBC NCL and Rank is 2184 According to opportunities for placements ….so which college should i prefer among the following and Anyone plz suggest good college aaprt from these according to my Gate score ?? nit surathkal NIT calicut IIT Indore MS IIT ropar IIT patna IIT Gandhinagar IIIT allahabad IIIT Banglore MS

My gate score is 600 OBC NCL and Rank is 2184According to opportunities for placements ….so which college should i prefer among the following and Anyone plz suggest goo...

Gopi Thawre

499 views

Gopi Thawre asked Apr 11, 2019

0 votes

0 answers

4429

Ullman (TOC) Edition 3 Exercise 7.1 Question 4 (Page No. 277)
Begin with the grammar$:$ $S\rightarrow AAA|B$ $A\rightarrow aA|B$ $B\rightarrow \in$ Eliminate $\in-$productions. Eliminate any unit productions in the resulting grammar. Eliminate any useless symbols in the resulting grammar. Put the resulting grammar into Chomsky Normal Form.

Begin with the grammar$:$$S\rightarrow AAA|B$$A\rightarrow aA|B$$B\rightarrow \in$ Eliminate $\in-$productions.Eliminate any unit productions in the resulting grammar.El...

admin

207 views

admin asked Apr 11, 2019

0 votes

0 answers

4430

Ullman (TOC) Edition 3 Exercise 7.1 Question 3 (Page No. 277)
Begin with the grammar$:$ $S\rightarrow 0A0|1B1|BB$ $A\rightarrow C$ $B\rightarrow S|A$ $C\rightarrow S|\in$ Eliminate $\in-$productions. Eliminate any unit productions in the resulting grammar. Eliminate any useless symbols in the resulting grammar. Put the resulting grammar into Chomsky Normal Form.

Begin with the grammar$:$$S\rightarrow 0A0|1B1|BB$$A\rightarrow C$$B\rightarrow S|A$$C\rightarrow S|\in$Eliminate $\in-$productions.Eliminate any unit productions in the ...

admin

227 views

admin asked Apr 11, 2019

0 votes

0 answers

4431

Ullman (TOC) Edition 3 Exercise 7.1 Question 2 (Page No. 275 - 276 - 277)
Begin with grammar$:$ $S\rightarrow ASB|\in$ $A\rightarrow aAS|a$ $B\rightarrow SbS|A|bb$ Eliminate $\in-$productions. Eliminate any unit productions in the resulting grammar. Eliminate any useless symbols in the resulting grammar. Put the resulting grammar into Chomsky Normal Form.

Begin with grammar$:$$S\rightarrow ASB|\in$$A\rightarrow aAS|a$$B\rightarrow SbS|A|bb$Eliminate $\in-$productions.Eliminate any unit productions in the resulting grammar....

admin

254 views

admin asked Apr 11, 2019

0 votes

0 answers

4432

Allen Carrer Institute: TOC1
How many no. of states in DFA for the following required expression? $(a + b + c) (a + b + c) (a + b + c) (a + b + c) ……… (n – 2)$ times $(a + b + c)^{+}$ $(1) $ $n – 1$ $(2) $ $n$ $(3) $ $n + 1$ $(4) $ $n + 2$ Plz confirm me the answer . Is it $(n-1)$ or $n ?$

How many no. of states in DFA for the following required expression?$(a + b + c) (a + b + c) (a + b + c) (a + b + c) ……… (n – 2)$ times $(a + b + c)^{+}$$(1) $$n ...

srestha

452 views

srestha asked Apr 11, 2019

0 votes

0 answers

4433

Kenneth Rosen Edition 7 Exercise 2.3 Question 74 (Page No. 155)
Prove or disprove each of these statements about the floor and ceiling functions. $\left \lfloor \left \lceil x \right \rceil \right \rfloor = \left \lceil x \right \rceil$ for all real numbers $x.$ ... $x$ and $y.$

Prove or disprove each of these statements about the floor and ceiling functions.$\left \lfloor \left \lceil x \right \rceil \right \rfloor = \left \lceil x \right \rceil...

Pooja Khatri

377 views

Pooja Khatri asked Apr 11, 2019

0 votes

0 answers

4434

Kenneth Rosen Edition 7 Exercise 2.3 Question 73 (Page No. 155)
Prove or disprove each of these statements about the floor and ceiling functions. $\left \lceil \left \lfloor x \right \rfloor \right \rceil = \left \lfloor x \right \rfloor$ for all real number $x.$ ... $x.$

Prove or disprove each of these statements about the floor and ceiling functions.$\left \lceil \left \lfloor x \right \rfloor \right \rceil = \left \lfloor x \right \rflo...

Pooja Khatri

294 views

Pooja Khatri asked Apr 11, 2019

0 votes

0 answers

4435

Kenneth Rosen Edition 7 Exercise 2.3 Question 71 (Page No. 155)
Let $S$ be a subset of a universal set $U$. The characteristic function $f_{s}$ of $S$ is the function from $U$ to the set $\left \{ 0,1 \right \}$ such that $f_{S}(x)=1$ if $x$ belongs to $S$ and $f_S(x)=0$ if $x$ does not belong to $S$. Let $A$ ... $f_{A \oplus B}(x) = f_{A}(x) + f_{B}(x)- 2 f_{A}(x) f_{B}(x) $

Let $S$ be a subset of a universal set $U$. The characteristic function $f_{s}$ of $S$ is the function from $U$ to the set $\left \{ 0,1 \right \}$ such that $f_{S}(x)=1$...

Pooja Khatri

276 views

Pooja Khatri asked Apr 11, 2019

0 votes

0 answers

4436

Kenneth Rosen Edition 7 Exercise 2.3 Question 70 (Page No. 155)
Suppose that $f$ is an invertible function from $Y$ to $Z$ and $g$ is an invertible function from $X$ to $Y$. Show that the inverse of the composition $fog$ is given by $(fog)^{-1} = g^{-1} o f^{-1}.$

Suppose that $f$ is an invertible function from $Y$ to $Z$ and $g$ is an invertible function from $X$ to $Y$. Show that the inverse of the composition $fog$ is given by $...

Pooja Khatri

222 views

Pooja Khatri asked Apr 11, 2019

0 votes

0 answers

4437

Kenneth Rosen Edition 7 Exercise 2.3 Question 68 (Page No. 155)
Draw graphs of each of these functions. $f(x) =$ $\left \lceil 3x-2 \right \rceil$ $f(x) =$ $\left \lceil 0.2x \right \rceil$ $f(x) =$ $\left \lfloor -1/x \right \rfloor$ $f(x) =$ $\left \lfloor x^2 \right \rfloor$ ... $f(x) =$ $\left \lfloor 2\left \lceil x/2 \right \rceil +1/2\right \rfloor$

Draw graphs of each of these functions.$f(x) =$ $\left \lceil 3x-2 \right \rceil$$f(x) =$ $\left \lceil 0.2x \right \rceil$$f(x) =$ $\left \lfloor -1/x \right \rfloor$$f(...

Pooja Khatri

210 views

Pooja Khatri asked Apr 11, 2019

0 votes

0 answers

4438

Kenneth Rosen Edition 7 Exercise 2.3 Question 67 (Page No. 155)
Draw graphs of each of these functions. $f(x) =$ $\left \lfloor x+1/2 \right \rfloor$ $f(x) =$ $\left \lfloor 2x+1 \right \rfloor$ $f(x) =$ $\left \lceil x/3 \right \rceil$ $f(x) =$ $\left \lceil 1/x \right \rceil$ ... $f(x) =$ $\left \lceil \left \lfloor x-12 \right \rfloor + 1/2\right \rceil$

Draw graphs of each of these functions.$f(x) =$ $\left \lfloor x+1/2 \right \rfloor$$f(x) =$ $\left \lfloor 2x+1 \right \rfloor$$f(x) =$ $\left \lceil x/3 \right \rceil$$...

Pooja Khatri

165 views

Pooja Khatri asked Apr 11, 2019

0 votes

0 answers

4439

Kenneth Rosen Edition 7 Exercise 2.3 Question 66 (Page No. 155)
Draw the graph of the function $f(n) =$ $\left \lceil x \right \rceil +\left \lceil x/2 \right \rceil$ from $R$ to $R$

Draw the graph of the function $f(n) =$ $\left \lceil x \right \rceil +\left \lceil x/2 \right \rceil$ from $R$ to $R$

Pooja Khatri

178 views

Pooja Khatri asked Apr 11, 2019

0 votes

0 answers

4440

Kenneth Rosen Edition 7 Exercise 2.3 Question 65 (Page No. 155)
Draw the graph of the function $f(n) =$\left \lfloor x \right \rfloor +\left \lfloor x/2 \right \rfloor$ from $R$ to $R$

Draw the graph of the function $f(n) =$$\left \lfloor x \right \rfloor +\left \lfloor x/2 \right \rfloor$ from $R$ to $R$

Pooja Khatri

192 views

Pooja Khatri asked Apr 11, 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