Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Filter
No answer
No selected answer
No upvoted answer
Previous GATE
Featured
Recent questions without answers
0
votes
0
answers
4171
Michael Sipser Edition 3 Exercise 1 Question 72 (Page No. 93)
Let $M_{1}$ and $M_{2}$ be $\text{DFA's}$ that have $k_{1}$ and $k_{2}$ states, respectively, and then let $U = L(M_{1})\cup L(M_{2}).$ Show that if $U\neq\phi$ then $U$ contains some string $s,$ where $|s| < max(k1, k2).$ Show that if $U\neq\sum^{*},$ then $U$ excludes some string $s,$ where $|s| < k1k2.$
Let $M_{1}$ and $M_{2}$ be $\text{DFA's}$ that have $k_{1}$ and $k_{2}$ states, respectively, and then let $U = L(M_{1})\cup L(M_{2}).$Show that if $U\neq\phi$ then $U$ c...
admin
320
views
admin
asked
Apr 30, 2019
Theory of Computation
michael-sipser
theory-of-computation
finite-automata
regular-language
proof
descriptive
+
–
1
votes
0
answers
4172
Michael Sipser Edition 3 Exercise 1 Question 69 (Page No. 93)
Let $\sum=\{0,1\}.$ Let $WW_{k}=\{ww|w\in \sum^{*}$ and $w$ is of length $k\}.$ Show that for each $k,$ no DFA can recognize $WW_{k}$ with fewer than $2^{k}$ states. Describe a much smaller $NFA$ for $\overline{WW_{k}},$ the complement of $WW_{k}.$
Let $\sum=\{0,1\}.$ Let $WW_{k}=\{ww|w\in \sum^{*}$ and $w$ is of length $k\}.$Show that for each $k,$ no DFA can recognize $WW_{k}$ with fewer than $2^{k}$ states.Descri...
admin
333
views
admin
asked
Apr 30, 2019
Theory of Computation
michael-sipser
theory-of-computation
finite-automata
proof
descriptive
+
–
0
votes
0
answers
4173
Michael Sipser Edition 3 Exercise 1 Question 68 (Page No. 93)
In the traditional method for cutting a deck of playing cards, the deck is arbitrarily split two parts, which are exchanged beforereassembling the deck. In a more complex cut, called $\text{Scarne's cut,}$ the deck is broken into three parts ... $ CUT(CUT(B)).}$ Show that the class of regular languages is closed under $\text{CUT}.$
In the traditional method for cutting a deck of playing cards, the deck is arbitrarily split two parts, which are exchanged beforereassembling the deck. In a more complex...
admin
516
views
admin
asked
Apr 30, 2019
Theory of Computation
michael-sipser
theory-of-computation
regular-language
scarnes-cut
proof
descriptive
+
–
0
votes
0
answers
4174
Michael Sipser Edition 3 Exercise 1 Question 67 (Page No. 93)
Let the rotational closure of language $A$ be $RC(A) = \{yx| xy ∈ A\}.$ Show that for any language $A,$ we have $RC(A) = RC(RC(A)).$ Show that the class of regular languages is closed under rotational closure.
Let the rotational closure of language $A$ be $RC(A) = \{yx| xy ∈ A\}.$Show that for any language $A,$ we have $RC(A) = RC(RC(A)).$Show that the class of regular langua...
admin
406
views
admin
asked
Apr 30, 2019
Theory of Computation
michael-sipser
theory-of-computation
regular-language
rotational-closure-of-language
descriptive
+
–
0
votes
0
answers
4175
Michael Sipser Edition 3 Exercise 1 Question 66 (Page No. 93)
A $\text{homomorphism}$ is a function $f : Σ→Γ^{*}$ from one alphabet to strings overanother alphabet. We can extend $f$ to operate on strings by defining $f(w) = f(w_{1})f(w_{2})...f(w_{n}),$ ... Is it a DFA in every case$?$ Show, by giving an example, that the class of non-regular languages is not closed under homomorphism.
A $\text{homomorphism}$ is a function $f : Σ→Γ^{*}$ from one alphabet to strings overanother alphabet. We can extend $f$ to operate on strings by defining $f(w) = f(w...
admin
577
views
admin
asked
Apr 30, 2019
Theory of Computation
michael-sipser
theory-of-computation
finite-automata
homomorphism
descriptive
+
–
0
votes
0
answers
4176
Michael Sipser Edition 3 Exercise 1 Question 65 (Page No. 93)
Prove that for each $n > 0,$ a language $B_{n}$ exists where $B_{n}$ is recognizable by an $\text{NFA}$ that has $n$ states, and if $B_{n} = A_{1}\cup...\cup A_{k},$ for regular languages $A_{i},$ then at least one of the $A_{i}$ requires a $\text{DFA}$ with exponentially many states$.$
Prove that for each $n 0,$ a language $B_{n}$ exists where$B_{n}$ is recognizable by an $\text{NFA}$ that has $n$ states, andif $B_{n} = A_{1}\cup...\cup A_{k},$ for reg...
admin
295
views
admin
asked
Apr 30, 2019
Theory of Computation
michael-sipser
theory-of-computation
finite-automata
descriptive
+
–
0
votes
0
answers
4177
Michael Sipser Edition 3 Exercise 1 Question 64 (Page No. 92)
Let $N$ be an $\text{NFA}$ with $k$ states that recognizes some language $A.$ Show that if $A$ is nonempty, A contains some string of length at most k. Show, by giving an example, that $\text{part (a)}$ is not necessarily ... ;s shortest member strings are of length exponential in $k.$ Come as close to the bound in $(c)$ as you can$.$
Let $N$ be an $\text{NFA}$ with $k$ states that recognizes some language $A.$Show that if $A$ is nonempty, A contains some string of length at most k.Show, by giving an e...
admin
574
views
admin
asked
Apr 30, 2019
Theory of Computation
michael-sipser
theory-of-computation
finite-automata
descriptive
+
–
0
votes
0
answers
4178
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
341
views
admin
asked
Apr 30, 2019
Theory of Computation
michael-sipser
theory-of-computation
finite-automata
regular-language
descriptive
+
–
0
votes
0
answers
4179
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
218
views
admin
asked
Apr 30, 2019
Theory of Computation
michael-sipser
theory-of-computation
finite-automata
descriptive
+
–
0
votes
0
answers
4180
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
289
views
admin
asked
Apr 30, 2019
Theory of Computation
michael-sipser
theory-of-computation
finite-automata
proof
descriptive
+
–
0
votes
0
answers
4181
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
592
views
admin
asked
Apr 30, 2019
Theory of Computation
michael-sipser
theory-of-computation
finite-automata
synchronizable-dfa
descriptive
+
–
0
votes
0
answers
4182
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
218
views
admin
asked
Apr 30, 2019
Theory of Computation
michael-sipser
theory-of-computation
regular-language
proof
descriptive
+
–
0
votes
0
answers
4183
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
257
views
admin
asked
Apr 30, 2019
Theory of Computation
michael-sipser
theory-of-computation
regular-language
proof
descriptive
+
–
0
votes
0
answers
4184
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
327
views
admin
asked
Apr 30, 2019
Theory of Computation
michael-sipser
theory-of-computation
finite-automata
regular-language
proof
descriptive
+
–
0
votes
0
answers
4185
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
282
views
admin
asked
Apr 30, 2019
Theory of Computation
michael-sipser
theory-of-computation
finite-automata
regular-language
proof
descriptive
+
–
1
votes
0
answers
4186
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
390
views
admin
asked
Apr 30, 2019
Theory of Computation
michael-sipser
theory-of-computation
finite-automata
finite-automata
proof
descriptive
+
–
0
votes
0
answers
4187
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
296
views
admin
asked
Apr 30, 2019
Theory of Computation
michael-sipser
theory-of-computation
finite-automata
proof
descriptive
+
–
1
votes
0
answers
4188
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
191
views
admin
asked
Apr 30, 2019
Theory of Computation
michael-sipser
theory-of-computation
finite-automata
finite-state-transducer
proof
descriptive
+
–
1
votes
0
answers
4189
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
250
views
admin
asked
Apr 30, 2019
Theory of Computation
michael-sipser
theory-of-computation
finite-automata
regular-language
proof
descriptive
+
–
0
votes
0
answers
4190
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
312
views
admin
asked
Apr 30, 2019
Theory of Computation
michael-sipser
theory-of-computation
finite-automata
regular-language
proof
+
–
0
votes
0
answers
4191
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
490
views
admin
asked
Apr 30, 2019
Theory of Computation
michael-sipser
theory-of-computation
finite-automata
regular-language
proof
+
–
0
votes
0
answers
4192
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
203
views
admin
asked
Apr 30, 2019
Theory of Computation
michael-sipser
theory-of-computation
finite-automata
regular-language
descriptive
+
–
0
votes
0
answers
4193
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
207
views
admin
asked
Apr 30, 2019
Theory of Computation
michael-sipser
theory-of-computation
finite-automata
regular-language
descriptive
+
–
0
votes
0
answers
4194
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
663
views
admin
asked
Apr 30, 2019
Theory of Computation
michael-sipser
theory-of-computation
finite-automata
regular-language
proof
descriptive
+
–
0
votes
0
answers
4195
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.....
661
views
kd.....
asked
Apr 30, 2019
Databases
sql
databases
relational-algebra
+
–
0
votes
0
answers
4196
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
566
views
ranarajesh495
asked
Apr 29, 2019
0
votes
0
answers
4197
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
329
views
admin
asked
Apr 28, 2019
Theory of Computation
michael-sipser
theory-of-computation
finite-automata
regular-language
+
–
0
votes
0
answers
4198
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
452
views
admin
asked
Apr 28, 2019
Theory of Computation
michael-sipser
theory-of-computation
finite-automata
regular-language
perfect-shuffle
+
–
0
votes
0
answers
4199
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
354
views
admin
asked
Apr 28, 2019
Theory of Computation
michael-sipser
theory-of-computation
finite-automata
regular-language
prefix-free-property
+
–
0
votes
0
answers
4200
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
366
views
admin
asked
Apr 28, 2019
Theory of Computation
michael-sipser
theory-of-computation
finite-automata
proof
+
–
Page:
« prev
1
...
135
136
137
138
139
140
141
142
143
144
145
...
590
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register