Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged ullman
0
votes
0
answers
241
Ullman (TOC) Edition 3 Exercise 5.1 Question 5 (Page No. 182)
Let $T=\{0,1(,),+,*,\phi,e\}.$ We may think of $T$ as the set of symbols used by regular expressions over alphabet $\{0,1\};$ the only difference is that we use $e$ for symbol $\in,$ to avoid potential ... Your task is to design a CFG with set of terminals $T$ that generates exactly the regular expressions with alphabet $\{0,1\}.$
Let $T=\{0,1(,),+,*,\phi,e\}.$ We may think of $T$ as the set of symbols used by regular expressions over alphabet $\{0,1\};$ the only difference is that we use $e$ for s...
admin
255
views
admin
asked
Apr 6, 2019
Theory of Computation
ullman
theory-of-computation
regular-expression
context-free-grammar
+
–
0
votes
0
answers
242
Ullman (TOC) Edition 3 Exercise 5.1 Question 4 (Page No. 182)
A CFG is said to be right-linear if each production body has at most one variable and that variable is at the right end. That is all productions of a right-linear grammar are of the form $A\rightarrow wB$ ... regular language has a right-linear grammar. Hint$:$Start with a DFA and let the variables of the grammar represent states.
A CFG is said to be right-linear if each production body has at most one variable and that variable is at the right end. That is all productions of a right-linear grammar...
admin
326
views
admin
asked
Apr 6, 2019
Theory of Computation
ullman
theory-of-computation
context-free-grammar
regular-language
+
–
0
votes
0
answers
243
Ullman (TOC) Edition 3 Exercise 5.1 Question 3 (Page No. 182)
Show that every regular language is a context-free language. Hint$:$ Construct a $CFG$ by induction on the number of operators in the regular expression.
Show that every regular language is a context-free language. Hint$:$ Construct a $CFG$ by induction on the number of operators in the regular expression.
admin
218
views
admin
asked
Apr 6, 2019
Theory of Computation
ullman
theory-of-computation
regular-language
context-free-language
+
–
0
votes
0
answers
244
Ullman (TOC) Edition 3 Exercise 5.1 Question 2 (Page No. 182)
The following grammar generates the language of regular expression $0^{*}1(0+1)^{*}:$ $S\rightarrow A1B$ $A\rightarrow 0A|\in$ $B\rightarrow B|1B|\in$ Give leftmost and rightmost derivations of the following strings$:$ $00101$ $1001$ $00011$
The following grammar generates the language of regular expression $0^{*}1(0+1)^{*}:$$S\rightarrow A1B$$A\rightarrow 0A|\in$$B\rightarrow B|1B|\in$Give leftmost and right...
admin
222
views
admin
asked
Apr 6, 2019
Theory of Computation
ullman
theory-of-computation
context-free-grammar
regular-expression
+
–
0
votes
0
answers
245
Ullman (TOC) Edition 3 Exercise 5.1 Question 1 (Page No. 181 - 182)
Design context-free grammars for the following languages$:$ The set $\{0^{n}1^{n}|n\geq 1,\}$that is the set of all strings of one or more $0's$ followed by an equal number of $1's.$ ... $0's$ as $1's.$
Design context-free grammars for the following languages$:$The set $\{0^{n}1^{n}|n\geq 1,\}$that is the set of all strings of one or more $0's$ followed by an equal numbe...
admin
299
views
admin
asked
Apr 6, 2019
Theory of Computation
ullman
theory-of-computation
context-free-grammar
context-free-language
+
–
0
votes
0
answers
246
Ullman (TOC) Edition 3 Exercise 4.4 Question 3 (Page No. 166)
Suppose that $p$ and $q$ are distinguishable states of a given DFA $A$ with $n$ states. As a function of $n$ what is the tightest upper bound on how long the shortest string that distinguishes $p$ from $q$ can be$?$
Suppose that $p$ and $q$ are distinguishable states of a given DFA $A$ with $n$ states. As a function of $n$ what is the tightest upper bound on how long the shortest str...
admin
358
views
admin
asked
Apr 6, 2019
Theory of Computation
ullman
theory-of-computation
finite-automata-dfa
+
–
0
votes
1
answer
247
Ullman (TOC) Edition 3 Exercise 4.4 Question 2 (Page No. 165 - 166)
Below figure is the transition table of a DFA. Draw the table of distinguishabilities for this automaton Construct the minimum – state equivalent DFA.
Below figure is the transition table of a DFA. Draw the table of distinguishabilities for this automaton Construct the minimum – state equivalent DFA.
admin
747
views
admin
asked
Apr 6, 2019
Theory of Computation
ullman
theory-of-computation
finite-automata-dfa
+
–
0
votes
0
answers
248
Ullman (TOC) Edition 3 Exercise 4.4 Question 1 (Page No. 165)
Below figure is the transition table of a DFA. Draw the table of distinguishabilities for this automaton Construct the minimum – state equivalent DFA.
Below figure is the transition table of a DFA. Draw the table of distinguishabilities for this automaton Construct the minimum – state equivalent DFA.
admin
730
views
admin
asked
Apr 6, 2019
Theory of Computation
ullman
theory-of-computation
finite-automata-dfa
+
–
0
votes
0
answers
249
Ullman (TOC) Edition 3 Exercise 4.3 Question 5 (Page No. 155)
Give an algorithm to tell for two regular languages $L_{1}$ and $L_{2}$ over the same alphabet $\sum,$ whether there is any string in $\sum^{*}$ that is in neither $L_{1}$ nor $L_{2}.$
Give an algorithm to tell for two regular languages $L_{1}$ and $L_{2}$ over the same alphabet $\sum,$ whether there is any string in $\sum^{*}$ that is in neither $L_{1}...
admin
204
views
admin
asked
Apr 6, 2019
Theory of Computation
ullman
theory-of-computation
regular-language
descriptive
+
–
0
votes
0
answers
250
Ullman (TOC) Edition 3 Exercise 4.3 Question 4 (Page No. 155)
Give an algorithm to tell whether two regular languages $L_{1}$ and $L_{2}$ have at least one string in common.
Give an algorithm to tell whether two regular languages $L_{1}$ and $L_{2}$ have at least one string in common.
admin
150
views
admin
asked
Apr 6, 2019
Theory of Computation
ullman
theory-of-computation
descriptive
+
–
0
votes
0
answers
251
Ullman (TOC) Edition 3 Exercise 4.3 Question 3 (Page No. 155)
Suppose $L$ is a regular language with alphabet $\sum.$ Give an algorithm to tell whether $L=\sum^{*},i.e,$ all strings over it's alphabet.
Suppose $L$ is a regular language with alphabet $\sum.$ Give an algorithm to tell whether $L=\sum^{*},i.e,$ all strings over it's alphabet.
admin
272
views
admin
asked
Apr 6, 2019
Theory of Computation
ullman
theory-of-computation
regular-language
descriptive
+
–
0
votes
0
answers
252
Ullman (TOC) Edition 3 Exercise 4.3 Question 2 (Page No. 155)
Give an algorithm to tell whether a regular language $L$ contains at least $100$ strings.
Give an algorithm to tell whether a regular language $L$ contains at least $100$ strings.
admin
203
views
admin
asked
Apr 6, 2019
Theory of Computation
ullman
theory-of-computation
regular-language
descriptive
+
–
0
votes
0
answers
253
Ullman (TOC) Edition 3 Exercise 4.3 Question 1 (Page No. 155)
Give an algorithm to tell whether a regular language $L$ is infinite. Hint$:$Use the pumping lemma to show that if the language contains any string whose length is above a certain lower limit, then the language must be infinite.
Give an algorithm to tell whether a regular language $L$ is infinite. Hint$:$Use the pumping lemma to show that if the language contains any string whose length is above ...
admin
254
views
admin
asked
Apr 6, 2019
Theory of Computation
ullman
theory-of-computation
regular-language
descriptive
+
–
0
votes
0
answers
254
Ullman (TOC) Edition 3 Exercise 4.2 Question 14 (Page No. 149 - 150)
We described the $"$product construction$"$ that took two DFA's and constructed one DFA whose language is intersection of the languages of the first two. Show how to perform the product construction on ... the product construction so the resulting DFA accepts the union of the languages of the two given DFA's.
We described the $"$product construction$"$ that took two DFA's and constructed one DFA whose language is intersection of the languages of the first two.Show how to perfo...
admin
215
views
admin
asked
Apr 6, 2019
Theory of Computation
ullman
theory-of-computation
regular-language
regular-expression
+
–
1
votes
0
answers
255
Ullman (TOC) Edition 3 Exercise 4.2 Question 13 (Page No. 149)
We can use closure properties to help prove certain languages are not regular. Start with the fact that the language $L_{0n1n}=\{0^{n}1^{n}|n\geq 0\}$ is not a regular set. Prove the following languages not to be regular by transforming them using operations known to ... $\{0^{n}1^{m}2^{n-m}|n\geq m\geq 0\}$
We can use closure properties to help prove certain languages are not regular. Start with the fact that the language $L_{0n1n}=\{0^{n}1^{n}|n\geq 0\}$ is not a regular se...
admin
215
views
admin
asked
Apr 6, 2019
Theory of Computation
ullman
theory-of-computation
regular-language
regular-expression
+
–
0
votes
0
answers
256
Ullman (TOC) Edition 3 Exercise 4.2 Question 12 (Page No. 149)
Let $w_{1}=a_{0}a_{0}a_{1},$ and $w_{i}=w_{i-1}w_{i-1}a_{i}$ for all $i>1.$For instance,$w_{3}=a_{0}a_{0}a_{1}a_{0}a_{0}a_{1}a_{2}a_{0}a_{0}a_{1}a_{0}a_{0}a_{1}a_{2}a_{3}.$ The shortest ... is $O(n^{2}).$ Find such an expression. Hint $:$ Find $n$ languages, each with regular expressions of length $O(n).$ Whose intersection is $L.$
Let $w_{1}=a_{0}a_{0}a_{1},$ and $w_{i}=w_{i-1}w_{i-1}a_{i}$ for all $i>1.$For instance,$w_{3}=a_{0}a_{0}a_{1}a_{0}a_{0}a_{1}a_{2}a_{0}a_{0}a_{1}a_{0}a_{0}a_{1}a_{2}a_{3}...
admin
181
views
admin
asked
Apr 6, 2019
Theory of Computation
ullman
theory-of-computation
regular-language
regular-expression
+
–
0
votes
0
answers
257
Ullman (TOC) Edition 3 Exercise 4.2 Question 11 (Page No. 149)
Show that the regular languages are closed under the following operation$:$ $\text{cycle(L)={we can write w as w = xy,such that yx is in L}}.$ For example if $L=\{01,011\},$then $cycle(L)=\{01,10,011,110,101\}.$ Hint$:$ Start with a DFA for $L$ and construct an $\in-NFA$ for $cycle(L).$
Show that the regular languages are closed under the following operation$:$ $\text{cycle(L)={we can write w as w = xy,such that yx is in L}}.$ For example if $L=\{01,011\...
admin
186
views
admin
asked
Apr 6, 2019
Theory of Computation
ullman
theory-of-computation
regular-language
regular-expression
+
–
0
votes
0
answers
258
Ullman (TOC) Edition 3 Exercise 4.2 Question 10 (Page No. 149)
Suppose that $L$ is any language not necessarily regular whose alphabet is $\{0\};$i.e. the strings of $L$ consist of $0's$ only. Prove that $L^{*}$ is regular. Hint$:$ At first this theorem sounds preposterous. However, an example will help you see ... use copy of $000$ and $(j-3)/2$ copies of $00.$ Thus ,$L^{*}=$ $\in + 000^{*}.$
Suppose that $L$ is any language not necessarily regular whose alphabet is $\{0\};$i.e. the strings of $L$ consist of $0's$ only. Prove that $L^{*}$ is regular. Hint$:$ A...
admin
147
views
admin
asked
Apr 6, 2019
Theory of Computation
ullman
theory-of-computation
regular-language
regular-expression
+
–
0
votes
0
answers
259
Ullman (TOC) Edition 3 Exercise 4.2 Question 9 (Page No. 148 - 149)
We can generalize question $8$ to a number of functions that determine how much of the string we take.If $f$ is a function of integers, define $f(L)$ ... what we do not take. $f(n)=2^{n}(i.e,$ what we take has length equal to the logarithm of what we leave$).$
We can generalize question $8$ to a number of functions that determine how much of the string we take.If $f$ is a function of integers, define $f(L)$ to be $\text{\{w| fo...
admin
189
views
admin
asked
Apr 6, 2019
Theory of Computation
ullman
theory-of-computation
regular-language
regular-expression
+
–
0
votes
0
answers
260
Ullman (TOC) Edition 3 Exercise 4.2 Question 8 (Page No. 148)
Let $L$ be a language.Define $\text{half(L)}$ to be the set of first halves of strings in $L,$ that is,$\{w|\text{for some x such that |x|=|w|,we have wx in L}\}.$For example,if $L=\{\in,0010,011,010110\}$ then ... that odd-length strings do not contribute to $\text{half(L)}$Prove that if $L$ is a regular language,so is $\text{half(L)}.$
Let $L$ be a language.Define $\text{half(L)}$ to be the set of first halves of strings in $L,$ that is,$\{w|\text{for some x such that |x|=|w|,we have wx in L}\}.$For exa...
admin
457
views
admin
asked
Apr 4, 2019
Theory of Computation
ullman
theory-of-computation
regular-expression
regular-language
+
–
0
votes
0
answers
261
Ullman (TOC) Edition 3 Exercise 4.2 Question 7 (Page No. 148)
If $w=a_{1}a_{2}.....a_{n}$ and $x=b_{1}b_{2}....b_{n}$ are strings of the same length, define $alt(w,x)$ to be the string in which the symbols of $w$ and $x$ alternate starting with $w$ ... in $L$ and $x$ is any string in $M$ of the same length. Prove that if $L$ and $M$ are regular,so is $alt(L,M).$
If $w=a_{1}a_{2}.....a_{n}$ and $x=b_{1}b_{2}....b_{n}$ are strings of the same length, define $alt(w,x)$ to be the string in which the symbols of $w$ and $x$ alternate s...
admin
188
views
admin
asked
Apr 4, 2019
Theory of Computation
ullman
theory-of-computation
regular-language
regular-expression
+
–
0
votes
0
answers
262
Ullman (TOC) Edition 3 Exercise 4.2 Question 6 (Page No. 148)
Show that the regular languages are closed under the following operations$:$ $ min(L)=\big\{\text{w|w is in L, but no proper prefix of w is in L}\big\}.$ $ min(L)=\big\{\text{w|w is in L, and for no x other than $\in$ is wx in L}\big\}.$ $ init(L)=\big\{\text{w| for some x, wx is in L}\big\}.$
Show that the regular languages are closed under the following operations$:$$ min(L)=\big\{\text{w|w is in L, but no proper prefix of w is in L}\big\}.$$ min(L)=\big\{\te...
admin
201
views
admin
asked
Apr 4, 2019
Theory of Computation
ullman
theory-of-computation
regular-language
regular-expression
+
–
0
votes
0
answers
263
Ullman (TOC) Edition 3 Exercise 4.2 Question 5 (Page No. 148)
The operation of Problem $4.2.3$ is sometimes viewed as a $"$derivative and $a/L$ is written $\frac{dL}{da}.$ These derivatives apply to regular expressions in a manner similar to the way ordinary derivatives apply to arithmetic ... $\frac{dL}{d0}=\phi$ Characterize those languages $L$ for which $\frac{dL}{d0}=L$
The operation of Problem $4.2.3$ is sometimes viewed as a $"$derivative and $a/L$ is written $\frac{dL}{da}.$ These derivatives apply to regular expressions in a manner s...
admin
147
views
admin
asked
Apr 4, 2019
Theory of Computation
ullman
theory-of-computation
regular-language
regular-expression
+
–
0
votes
0
answers
264
Ullman (TOC) Edition 3 Exercise 4.2 Question 4 (Page No. 147)
Which of the following identities are true$?$ $(L/a)a=L($the left side represents the concatenation of the languages $L/a$ and $\{a\}).$ $a(a/L)=L($again concatenation with $\{a\},$ this time on the left, is intended$).$ $(La)/a=L$ $a/(aL)=L$
Which of the following identities are true$?$$(L/a)a=L($the left side represents the concatenation of the languages $L/a$ and $\{a\}).$$a(a/L)=L($again concatenation with...
admin
371
views
admin
asked
Apr 4, 2019
Theory of Computation
ullman
theory-of-computation
regular-language
+
–
0
votes
0
answers
265
Ullman (TOC) Edition 3 Exercise 4.2 Question 3 (Page No. 147)
If $L$ is a language and $a$ is a symbol, then $a/L$ is the set of strings $w$ such that $aw$ is in $L.$ For example if $L=\{a,aab,baa\},$ then $a/L=\{\in,ab\}.$ Prove that if $L$ is regular so is $a/L$ Hint $:$Remember that the regular languages are closed under reversal and under the quotient operation of Question $2.$
If $L$ is a language and $a$ is a symbol, then $a/L$ is the set of strings $w$ such that $aw$ is in $L.$ For example if $L=\{a,aab,baa\},$ then $a/L=\{\in,ab\}.$ Prove th...
admin
192
views
admin
asked
Apr 4, 2019
Theory of Computation
ullman
theory-of-computation
regular-language
+
–
0
votes
0
answers
266
Ullman (TOC) Edition 3 Exercise 4.2 Question 1 (Page No. 147)
Suppose $h$ is the homomorphism from the alphabet $\{0,1,2\}$ to the alphabet $\{a,b\}$ de fined by$:$ $h(0)=a;h(1)=ab,$ and $h(2)=ba.$ What is $h(0120)?$ What is $h(21120)?$ If $L$ is the language $L(01^{*}2),$ ... only the one string $ababa.$ What is $h^{-1}(L)?$ If $L$ is the language $L(a(ba)^{*}),$what is $h^{-1}(L)?$
Suppose $h$ is the homomorphism from the alphabet $\{0,1,2\}$ to the alphabet $\{a,b\}$ de fined by$:$ $h(0)=a;h(1)=ab,$ and $h(2)=ba.$What is $h(0120)?$What is $h(21120)...
admin
3.7k
views
admin
asked
Apr 4, 2019
Theory of Computation
ullman
theory-of-computation
regular-language
regular
+
–
0
votes
0
answers
267
Ullman (TOC) Edition 3 Exercise 4.1 Question 4 (Page No. 132)
When we try to apply the pumping lemma to a regular language, the $"$adversary wins$",$ and we cannot complete the proof. Show what goes wrong when we choose $L$ to be one of the following languages$:$ The empty set. $\{00,11\}$ $(00+11)^{*}$ $01^{*}0^{*}1$
When we try to apply the pumping lemma to a regular language, the $"$adversary wins$",$ and we cannot complete the proof. Show what goes wrong when we choose $L$ to be on...
admin
386
views
admin
asked
Apr 4, 2019
Theory of Computation
ullman
theory-of-computation
regular-language
+
–
0
votes
0
answers
268
Ullman (TOC) Edition 3 Exercise 4.1 Question 3 (Page No. 132)
Prove that the following are not regular languages. The set of strings of $0's$ and $1's$ beginning with a $1,$ such that when interpreted as an integer that integer is a prime. The set of strings of the form $0^{i}1^{j}$ such that the greatest common divisor of $i$ and $j$ is $1.$
Prove that the following are not regular languages.The set of strings of $0's$ and $1's$ beginning with a $1,$ such that when interpreted as an integer that integer is a ...
admin
334
views
admin
asked
Apr 4, 2019
Theory of Computation
ullman
theory-of-computation
regular-language
+
–
0
votes
0
answers
269
Ullman (TOC) Edition 3 Exercise 4.1 Question 2 (Page No. 132)
Prove that the following are not regular languages. $\{0^{n}|n$ is a perfect square $\}$ $\{0^{n}|n$ is a perfect cube $\}$ $\{0^{n}|n$ is a power of $2\}$ The set of strings of $0's$ and $1's$ whose length is ... . The set of strings of the form $w1^{n},$ where $w$ is a string of $0's$ and $1's$ of length $n.$
Prove that the following are not regular languages.$\{0^{n}|n$ is a perfect square $\}$$\{0^{n}|n$ is a perfect cube $\}$$\{0^{n}|n$ is a power of $2\}$The set of strings...
admin
298
views
admin
asked
Apr 4, 2019
Theory of Computation
ullman
theory-of-computation
regular-language
+
–
0
votes
0
answers
270
Ullman (TOC) Edition 3 Exercise 4.1 Question 1 (Page No. 131)
Prove that the following are not regular languages. $\{0^{n}1^{n}|n\geq 1\}.$This language, consisting of a string of $0's$ followed by an equal-length string of $1's,$ is the language $L_{01}$ we considered informally at the beginning of the ... are arbitrary integers$\}$. $\{0^{n}1^{m}|n\leq m\}$ $\{0^{n}1^{2n}|n\geq 1\}$
Prove that the following are not regular languages.$\{0^{n}1^{n}|n\geq 1\}.$This language, consisting of a string of $0's$ followed by an equal-length string of $1's,$ is...
admin
405
views
admin
asked
Apr 4, 2019
Theory of Computation
ullman
theory-of-computation
regular-language
+
–
Page:
« prev
1
...
4
5
6
7
8
9
10
11
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register