Recent questions without answers / GATE Overflow for GATE CSE

0 votes

0 answers

4201

Michael Sipser Edition 3 Exercise 1 Question 63 (Page No. 92)
Let $A$ be an infinite regular language. Prove that $A$ can be split into two infinite disjoint regular subsets. Let $B$ and $D$ be two languages. Write $B\subseteqq D$ if $B\subseteq D$ and $D$ contains infinitely many ... regular languages where $B\subseteqq D,$ then we can find a regular language $C$ where $B\subseteqq C\subseteqq D.$

Let $A$ be an infinite regular language. Prove that $A$ can be split into two infinite disjoint regular subsets.Let $B$ and $D$ be two languages. Write $B\subseteqq D$ if...

admin

346 views

admin asked Apr 30, 2019

0 votes

0 answers

4202

Michael Sipser Edition 3 Exercise 1 Question 62 (Page No. 92)
Let $\sum =\{a, b\}.$ For each $k\geq 1,$ let $D_{k}$ be the language consisting of all strings that have at least one a among the last $k$ symbols$.$Thus $D_{k}=\sum^{*}a(\sum \cup \epsilon)^{k-1}$.Describe a $\text{DFA}$ with at most $k+ 1$ states that recognizes $D_{k}$ in terms of both a state diagram and a formal description.

Let $\sum =\{a, b\}.$ For each $k\geq 1,$ let $D_{k}$ be the language consisting of all strings that have at least one a among the last $k$ symbols$.$Thus $D_{k}=\sum^{*}...

admin

221 views

admin asked Apr 30, 2019

0 votes

0 answers

4203

Michael Sipser Edition 3 Exercise 1 Question 61 (Page No. 92)
Let $Σ = \{a, b\}.$ For each $k\geq 1,$ let $C_{k}$ be the language consisting of all strings that contain an a exactly $k$ places from the right-hand end$.$ Thus $C_{k}=\sum^{*}a\sum^{k-1}.$ Prove that for each $k,$ $\text{no DFA}$ can recognize $C_{k}$ with fewer than $2^{k}$ states.

Let $Σ = \{a, b\}.$ For each $k\geq 1,$ let $C_{k}$ be the language consisting of all strings that contain an a exactly $k$ places from the right-hand end$.$ Thus $C_{k}...

admin

294 views

admin asked Apr 30, 2019

0 votes

0 answers

4204

Michael Sipser Edition 3 Exercise 1 Question 59 (Page No. 92)
Let $M = (Q, Σ, δ, q_{0}, F)$ be a $\text{DFA}$ and let $h$ be a state of $M$ called its $\text{ home }.$ A $\text{synchronizing sequence}$ for $M$ and $h$ is a string $s\in\sum^{*}$ ... $\text{DFA,}$ then it has a synchronizing sequence of length at most $k^{3}.$Can you improve upon this bound$?$

Let $M = (Q, Σ, δ, q_{0}, F)$ be a $\text{DFA}$ and let $h$ be a state of $M$ called its $\text{“home”}.$ A $\text{synchronizing sequence}$ for $M$ and $h$ is a str...

admin

617 views

admin asked Apr 30, 2019

0 votes

0 answers

4205

Michael Sipser Edition 3 Exercise 1 Question 58 (Page No. 92)
If $A$ is any language,let $A_{\frac{1}{2}-\frac{1}{3}}$ be the set of all strings in $A$ with their ,middle thirds removed so that $A_{\frac{1}{2}-\frac{1}{3}}=\{\text{xz|for some y,|x|=|y|=|z| and xyz $\in$ A\}}.$ Show that if $A$ is regular,then $A_{\frac{1}{2}-\frac{1}{3}}$ is not necessarily regular.

If $A$ is any language,let $A_{\frac{1}{2}-\frac{1}{3}}$ be the set of all strings in $A$ with their ,middle thirds removed so that$A_{\frac{1}{2}-\frac{1}{3}}=\{\text{xz...

admin

223 views

admin asked Apr 30, 2019

0 votes

0 answers

4206

Michael Sipser Edition 3 Exercise 1 Question 57 (Page No. 92)
If $A$ is any language,let $A_{\frac{1}{2}-}$ be the set of all first halves of strings in $A$ so that $A_{\frac{1}{2}-}=\{\text{x|for some y,|x|=|y| and xy $\in$ A\}}.$ Show that if $A$ is regular,then so is $A_{\frac{1}{2}-}.$

If $A$ is any language,let $A_{\frac{1}{2}-}$ be the set of all first halves of strings in $A$ so that $A_{\frac{1}{2}-}=\{\text{x|for some y,|x|=|y| and xy $\in$ A\}}.$...

admin

259 views

admin asked Apr 30, 2019

0 votes

0 answers

4207

Michael Sipser Edition 3 Exercise 1 Question 56 (Page No. 91)
If $A$ is a set of natural numbers and $k$ is a natural number greater than $1,$ let $B_{k}(A)=\{\text{w| w is the representation in base k of some number in A\}}.$ Here, we do not allow leading $0's$ in the representation ... a set $A$ for which $B_{2}(A)$ is regular but $B_{3}(A)$ is not regular$.$ Prove that your example works.

If $A$ is a set of natural numbers and $k$ is a natural number greater than $1,$ let $B_{k}(A)=\{\text{w| w is the representation in base k of some number in A\}}.$ Here,...

admin

331 views

admin asked Apr 30, 2019

0 votes

0 answers

4208

Michael Sipser Edition 3 Exercise 1 Question 53 (Page No. 91)
Let $\sum=\{0,1,+,=\}$ and $ADD=\{x=y+z|x,y,z$ $\text{are binary integers,and}$ $x$ $\text{is the sum of}$ $y$ $\text{and}$ $z\}.$ Show that $\text{ADD}$ is not a regular.

Let $\sum=\{0,1,+,=\}$ and $ADD=\{x=y+z|x,y,z$ $\text{are binary integers,and}$ $x$ $\text{is the sum of}$ $y$ $\text{and}$ $z\}.$ Show that $\text{ADD}$ is not a regular...

admin

287 views

admin asked Apr 30, 2019

1 votes

0 answers

4209

Michael Sipser Edition 3 Exercise 1 Question 52 (Page No. 91)
$\text{Myhill-Nerode theorem.}$ Refer to $\text{Question 51}.$Let $L$ be a language and let $X$ be a set of strings. Say that $X$ is $\text{pairwise distinguishable}$ by $L$ if every two distinct strings in $X$ are ... $\text{DFA}$ recognizing it$.$

$\text{Myhill–Nerode theorem.}$ Refer to $\text{Question 51}.$Let $L$ be a language and let $X$ be a set of strings. Say that $X$ is $\text{pairwise distinguishable}$ b...

admin

392 views

admin asked Apr 30, 2019

0 votes

0 answers

4210

Michael Sipser Edition 3 Exercise 1 Question 51 (Page No. 90)
Let $x$ and $y$ be strings and let $L$ be any language. We say that $x$ and $y$ are $\text{distinguishable}$ by $L$ if some string $z$ exists whereby exactly one of the strings $xz$ and $yz$ ... $≡L$ is an equivalence relation. A $\text{palindrome}$ is a string that reads the same forward and backward.

Let $x$ and $y$ be strings and let $L$ be any language. We say that $x$ and $y$ are $\text{distinguishable}$ by $L$ if some string $z$ exists whereby exactly one of the s...

admin

308 views

admin asked Apr 30, 2019

1 votes

0 answers

4211

Michael Sipser Edition 3 Exercise 1 Question 50 (Page No. 90)
Read the informal definition of the finite state transducer given in Question $24.$ Prove that $\text{no FST}$ can output $w^{R}$ for every input $w$ if the input and output alphabets are $\{0,1\}.$

Read the informal definition of the finite state transducer given in Question $24.$ Prove that $\text{no FST}$ can output $w^{R}$ for every input $w$ if the input and out...

admin

194 views

admin asked Apr 30, 2019

1 votes

0 answers

4212

Michael Sipser Edition 3 Exercise 1 Question 48 (Page No. 90)
Let $\sum = \{0,1\}$ and let $D = \{w|w$ $\text{contains an equal number of occurrences of the sub strings 01 and 10}\}.$ Thus $101\in D$ because $101$ contains a single $01$ and a single $10,$ but $1010\notin D$ because $1010$ contains two $10's$ and one $01.$ Show that $D$ is a regular language.

Let $\sum = \{0,1\}$ and let $D = \{w|w$ $\text{contains an equal number of occurrences of the sub strings 01 and 10}\}.$Thus $101\in D$ because $101$ contains a single ...

admin

254 views

admin asked Apr 30, 2019

0 votes

0 answers

4213

Michael Sipser Edition 3 Exercise 1 Question 47 (Page No. 90)
Let $\sum=\{1,\#\}$ and let $Y=\{w|w=x_{1}\#x_{2}\#...\#x_{k}$ $\text{for}$ $k\geq 0,$ $\text{each}$ $ x_{i}\in 1^{*},$ $\text{and}$ $x_{i}\neq x_{j}$ $\text{for}$ $i\neq j\}.$ Prove that $Y$ is not regular.

Let $\sum=\{1,\#\}$ and let $Y=\{w|w=x_{1}\#x_{2}\#...\#x_{k}$ $\text{for}$ $k\geq 0,$ $\text{each}$ $ x_{i}\in 1^{*},$ $\text{and}$ $x_{i}\neq x_{j}$ $\text{for}$ $i\...

admin

321 views

admin asked Apr 30, 2019

0 votes

0 answers

4214

Michael Sipser Edition 3 Exercise 1 Question 46 (Page No. 90)
Prove that the following languages are not regular. You may use the pumping lemma and the closure of the class of regular languages under union, intersection,and complement. $\{0^{n}1^{m}0^{n}|m,n\geq 0\}$ $\{0^{m}1^{n}|m\neq n\}$ $\{w|w\in\{0,1\}^{*} \text{is not a palindrome}\}$ $\{wtw|w,t\in\{0,1\}^{+}\}$

Prove that the following languages are not regular. You may use the pumping lemma and the closure of the class of regular languages under union, intersection,and compleme...

admin

497 views

admin asked Apr 30, 2019

0 votes

0 answers

4215

Michael Sipser Edition 3 Exercise 1 Question 45 (Page No. 90)
Let $\text{A/B = {w| wx ∈ A for some x ∈ B}}.$ Show that if $A$ is regular and $B$ is any language, then $\text{A/B}$ is regular.

Let $\text{A/B = {w| wx ∈ A for some x ∈ B}}.$ Show that if $A$ is regular and $B$ is any language, then $\text{A/B}$ is regular.

admin

204 views

admin asked Apr 30, 2019

0 votes

0 answers

4216

Michael Sipser Edition 3 Exercise 1 Question 44 (Page No. 90)
Let $B$ and $C$ be languages over $\sum = \{0, 1\}.$ Define $B\overset{1}{\leftarrow} C = \{w\in B|$ $\text{for some}$ $y\in C$, $\text{strings}$ $w$ $\text{and}$ $y$ $\text{contain equal numbers of}$ $1’s\}.$ Show that the class of regular languages is closed under the $\overset{1}{\leftarrow}$operation.

Let $B$ and $C$ be languages over $\sum = \{0, 1\}.$ Define $B\overset{1}{\leftarrow} C = \{w\in B|$ $\text{for some}$ $y\in C$, $\text{strings}$ $w$ $\text{and}$ $y$ $\...

admin

208 views

admin asked Apr 30, 2019

0 votes

0 answers

4217

Michael Sipser Edition 3 Exercise 1 Question 43 (Page No. 90)
Let $A$ be any language. Define $\text{DROP-OUT(A)}$ to be the language containing all strings that can be obtained by removing one symbol from a string in $A.$ ... $\text{Theorem 1.47.}$

Let $A$ be any language. Define $\text{DROP-OUT(A)}$ to be the language containing all strings that can be obtained by removing one symbol from a string in $A.$ Thus, $\t...

admin

671 views

admin asked Apr 30, 2019

0 votes

0 answers

4218

Self Doubt on SQL AND operator
Here why does the 5th query select * from employees natural join works_on where PID = 'X' AND PID='Y'; is not working The queries are The output are

Here why does the 5th query select * from employees natural join works_on where PID = 'X' AND PID='Y'; is not workingThe queries are The output are

kd.....

679 views

kd..... asked Apr 30, 2019

0 votes

0 answers

4219

Argument passing in function by assigning value to a variable as argument.
Can we assign a value to a variable in calling a function as function argument? Ex- Int Func c( int); Int i =3; Void main(){ Fun c ( i=3)} Int Func c (int x) { Int x++; return x; } Please pardon me as the code above is not accurate but can give an idea of what i am trying to ask.

Can we assign a value to a variable in calling a function as function argument?Ex- Int Func c( int); Int i =3; Void main(){ Fun c ( i=3)} Int Func c (int x) { Int x++; re...

ranarajesh495

604 views

ranarajesh495 asked Apr 29, 2019

0 votes

0 answers

4220

Michael Sipser Edition 3 Exercise 1 Question 42 (Page No. 89)
For languages $A$ and $B,$ let the $\text{shuffle}$ of $A$ and $B$ be the language $\{w| w = a_{1}b_{1} \ldots a_{k}b_{k},$ where $ a_{1} · · · a_{k} ∈ A $ and $b_{1} · · · b_{k} ∈ B,$ each $a_{i}, b_{i} ∈ Σ^{*}\}.$ Show that the class of regular languages is closed under shuffle.

For languages $A$ and $B,$ let the $\text{shuffle}$ of $A$ and $B$ be the language $\{w| w = a_{1}b_{1} \ldots a_{k}b_{k},$ where $ a_{1} · · · a_{k} ∈ A $ and $b_...

admin

335 views

admin asked Apr 28, 2019

0 votes

0 answers

4221

Michael Sipser Edition 3 Exercise 1 Question 41 (Page No. 89)
For languages $A$ and $B,$ let the $\text{perfect shuffle}$ of $A$ and $B$ be the language $\text{{$w| w = a_{1}b_{1} · · · a_{k}b_{k},$ where $a_{1} · · · a_{k} ∈ A$ and $b_{1} · · · b_{k} ∈ B,$ each $a_{i}, b_{i} ∈ Σ$}}.$ Show that the class of regular languages is closed under perfect shuffle.

For languages $A$ and $B,$ let the $\text{perfect shuffle}$ of $A$ and $B$ be the language$\text{{$w| w = a_{1}b_{1} · · · a_{k}b_{k},$ where $a_{1} · · · a_{k} ∈...

admin

472 views

admin asked Apr 28, 2019

0 votes

0 answers

4222

Michael Sipser Edition 3 Exercise 1 Question 40 (Page No. 89)
Recall that string $x$ is a $\text{prefix}$ of string $y$ if a string $z$ exists where $xz = y,$ and that $x$ is a $\text{proper prefix}$ of $y$ if in addition $x\neq y.$ In each of the following parts, we define an operation on a ... $\text{NOEXTEND(A) = {w ∈ A| w is not the proper prefix of any string in A}.}$

Recall that string $x$ is a $\text{prefix}$ of string $y$ if a string $z$ exists where $xz = y,$ and that $x$ is a $\text{proper prefix}$ of $y$ if in addition $x\neq y.$...

admin

361 views

admin asked Apr 28, 2019

0 votes

0 answers

4223

Michael Sipser Edition 3 Exercise 1 Question 39 (Page No. 89)
The construction in $\text{Theorem 1.54}$ shows that every $\text{GNFA}$ is equivalent to a $\text{GNFA}$ with only two states$.$ We can show that an opposite phenomenon occurs for $\text{DFAs.}$ Prove that for every $k > 1,$ a ... exists that is recognized by a $\text{DFA}$ with $k$ states but not by one with only $k − 1$ states$.$

The construction in $\text{Theorem 1.54}$ shows that every $\text{GNFA}$ is equivalent to a $\text{GNFA}$ with only two states$.$ We can show that an opposite phenomenon ...

admin

376 views

admin asked Apr 28, 2019

0 votes

0 answers

4224

Michael Sipser Edition 3 Exercise 1 Question 35 (Page No. 89)
Let $\sum_{2}=\begin{Bmatrix}\begin{bmatrix} 0\\0 \end{bmatrix},\begin{bmatrix} 0\\1 \end{bmatrix},\begin{bmatrix} 1 \\0 \end{bmatrix},\begin{bmatrix} 1 \\1 \end{bmatrix}\end{Bmatrix}.$ Here $\sum_{2}$ contains all columns of $0's$ ... $ is the reverse of the top row of $w$}\}.$ Show that $E$ is not regular$.$

Let $\sum_{2}=\begin{Bmatrix}\begin{bmatrix} 0\\0 \end{bmatrix},\begin{bmatrix} 0\\1 \end{bmatrix},\begin{bmatrix} 1 \\0 \end{bmatrix},\begin{bmatrix} 1 \\1 \end{bmatrix}...

admin

177 views

admin asked Apr 28, 2019

0 votes

0 answers

4225

Michael Sipser Edition 3 Exercise 1 Question 34 (Page No. 89)
Let $\sum_{2}=\begin{Bmatrix}\begin{bmatrix} 0\\0 \end{bmatrix},\begin{bmatrix} 0\\1 \end{bmatrix},\begin{bmatrix} 1 \\0 \end{bmatrix},\begin{bmatrix} 1 \\1 \end{bmatrix}\end{Bmatrix}.$ Here $\sum_{2}$ contains all columns of ... $\begin{bmatrix} 0\\0 \end{bmatrix}\notin D$ Show that $D$ is regular$.$

Let $\sum_{2}=\begin{Bmatrix}\begin{bmatrix} 0\\0 \end{bmatrix},\begin{bmatrix} 0\\1 \end{bmatrix},\begin{bmatrix} 1 \\0 \end{bmatrix},\begin{bmatrix} 1 \\1 \end{bmatrix}...

admin

239 views

admin asked Apr 28, 2019

0 votes

0 answers

4226

Michael Sipser Edition 3 Exercise 1 Question 33 (Page No. 89)
Let $\sum_{2}=\begin{Bmatrix}\begin{bmatrix} 0\\0 \end{bmatrix},\begin{bmatrix} 0\\1 \end{bmatrix},\begin{bmatrix} 1 \\0 \end{bmatrix},\begin{bmatrix} 1 \\1 \end{bmatrix}\end{Bmatrix}.$ Here $\sum_{2}$ contains all columns ... $C$ is regular. $\text{(You may assume the result claimed in question $31$})$

Let $\sum_{2}=\begin{Bmatrix}\begin{bmatrix} 0\\0 \end{bmatrix},\begin{bmatrix} 0\\1 \end{bmatrix},\begin{bmatrix} 1 \\0 \end{bmatrix},\begin{bmatrix} 1 \\1 \end{bmatrix}...

admin

257 views

admin asked Apr 28, 2019

1 votes

0 answers

4227

Michael Sipser Edition 3 Exercise 1 Question 32 (Page No. 88)
Let $\sum_{3}=\begin{Bmatrix}\begin{bmatrix} 0\\0 \\0 \end{bmatrix},\begin{bmatrix} 0\\0 \\1 \end{bmatrix},\begin{bmatrix} 0\\1 \\0 \end{bmatrix}, .,\begin{bmatrix} 1\\1 \\1 \end{bmatrix}\end{Bmatrix}.$ $\sum_{3}$ ... $B$ is regular. $\text{(Hint$:$Working with $B^{R}$ is easier. You may assume the result claimed in question $31$})$

Let $\sum_{3}=\begin{Bmatrix}\begin{bmatrix} 0\\0 \\0 \end{bmatrix},\begin{bmatrix} 0\\0 \\1 \end{bmatrix},\begin{bmatrix} 0\\1 \\0 \end{bmatrix},…….,\begin{bmatrix} ...

admin

497 views

admin asked Apr 28, 2019

0 votes

0 answers

4228

Michael Sipser Edition 3 Exercise 1 Question 31 (Page No. 88)
For any string $w = w_{1}w_{2} · · · w_{n},$ the reverse of $w,$ written $w^{R},$ is the string $w$ in reverse order$, w_{n} · · · w_{2}w_{1}.$ For any language $A,$ let $A^{R} = \{w^{R}| w\in A\}.$ Show that if $A$ is regular$,$ so is $A^{R}.$

For any string $w = w_{1}w_{2} · · · w_{n},$ the reverse of $w,$ written $w^{R},$ is the string $w$ in reverse order$, w_{n} · · · w_{2}w_{1}.$ For any language $A,...

admin

313 views

admin asked Apr 28, 2019

0 votes

0 answers

4229

CSIR UGC NET
Let $A$ be a $3 \times 3$ real matrix. Suppose 1 and -1 are two of the three Eigen values of $A$ and 18 is one of the Eigen values of $A^2+3 A$. Then Both $A$ and $A^2+3 A$ are invertible $A^2+3 A$ is invertible but $A$ is not invertible $A$ is invertible but $A^2+3 A$ is not invertible Both $\mathrm{A}$ and $A^2+3 A$ are not invertible.

Let $A$ be a $3 \times 3$ real matrix. Suppose 1 and -1 are two of the three Eigen values of $A$ and 18 is one of the Eigen values of $A^2+3 A$. ThenBoth $A$ and $A^2+3 A...

Hirak

567 views

Hirak asked Apr 28, 2019

0 votes

0 answers

4230

Ford-Fulkersons method:

Nandkishor3939

441 views

Nandkishor3939 asked Apr 28, 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