Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged peter-linz-edition4
0
votes
0
answers
151
Peter Linz Edition 4 Exercise 4.3 Question 19 (Page No. 124)
Are the following languages regular? (a) $L=$ {$uww^Rv:u,v,w∈ ${$a,b$}$^+$} (b) $L=$ {$uww^Rv:u,v,w∈ ${$a,b$}$^+$, $|u|\geq |v|$}
Are the following languages regular?(a) $L=$ {$uww^Rv:u,v,w∈ ${$a,b$}$^+$}(b) $L=$ {$uww^Rv:u,v,w∈ ${$a,b$}$^+$, $|u|\geq |v|$}
Naveen Kumar 3
152
views
Naveen Kumar 3
asked
Apr 12, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
+
–
0
votes
0
answers
152
Peter Linz Edition 4 Exercise 4.3 Question 18 (Page No. 124)
Apply the pigeonhole argument directly to the language in $L=$ {$ww^R:w∈Σ^+$}.
Apply the pigeonhole argument directly to the language in $L=$ {$ww^R:w∈Σ^+$}.
Naveen Kumar 3
161
views
Naveen Kumar 3
asked
Apr 12, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
pigeonhole-principle
+
–
0
votes
0
answers
153
Peter Linz Edition 4 Exercise 4.3 Question 17 (Page No. 124)
Let $L_1$ and $L_2$ be regular languages. Is the language $L =$ {$w : w ∈ L_1, w^R ∈ L_2$ necessarily regular?
Let $L_1$ and $L_2$ be regular languages. Is the language $L =$ {$w : w ∈ L_1, w^R ∈ L_2$ necessarily regular?
Naveen Kumar 3
114
views
Naveen Kumar 3
asked
Apr 12, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
+
–
1
votes
1
answer
154
Peter Linz Edition 4 Exercise 4.3 Question 16 (Page No. 123)
Is the following language regular? $L=$ {$w_1cw_2:w_1,w_2∈$ {$a,b$}$^*,w_1\neq w_2$}.
Is the following language regular? $L=$ {$w_1cw_2:w_1,w_2∈$ {$a,b$}$^*,w_1\neq w_2$}.
Naveen Kumar 3
297
views
Naveen Kumar 3
asked
Apr 12, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pumping-lemma
regular-language
closure-property
+
–
1
votes
0
answers
155
Peter Linz Edition 4 Exercise 4.3 Question 15 (Page No. 123)
Consider the languages below. For each, make a conjecture whether or not it is regular. Then prove your conjecture. (a) $L=$ {$a^nb^la^k:n+k+l \gt 5$} (b) $L=$ {$a^nb^la^k:n \gt 5,l> 3,k\leq l$} (c) $L=$ {$a^nb^l:n/l$ is an integer} (d) $L=$ ... $L=$ {$a^nb^l:n\geq 100,l\leq 100$} (g) $L=$ {$a^nb^l:|n-l|=2$}
Consider the languages below. For each, make a conjecture whether or not it is regular. Thenprove your conjecture.(a) $L=$ {$a^nb^la^k:n+k+l \gt 5$}(b) $L=$ {$a^nb^la^k:n...
Naveen Kumar 3
304
views
Naveen Kumar 3
asked
Apr 12, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
pumping-lemma
closure-property
+
–
0
votes
1
answer
156
Peter Linz Edition 4 Exercise 4.3 Question 13 (Page No. 123)
Show that the following language is not regular. $L=$ {$a^nb^k:n>k$} $\cup$ {$a^nb^k:n\neq k-1$}.
Show that the following language is not regular.$L=$ {$a^nb^k:n>k$} $\cup$ {$a^nb^k:n\neq k-1$}.
Naveen Kumar 3
277
views
Naveen Kumar 3
asked
Apr 11, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pumping-lemma
regular-language
closure-property
+
–
0
votes
1
answer
157
Peter Linz Edition 4 Exercise 4.3 Question 14 (Page No. 123)
Prove or disprove the following statement: If $L_1$ and $L_2$ are non regular languages, then $L_1 ∪ L_2$ is also non regular.
Prove or disprove the following statement: If $L_1$ and $L_2$ are non regular languages, then $L_1 ∪ L_2$ isalso non regular.
Naveen Kumar 3
377
views
Naveen Kumar 3
asked
Apr 11, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
pumping-lemma
+
–
0
votes
1
answer
158
Peter Linz Edition 4 Exercise 4.3 Question 12 (Page No. 123)
Apply the pumping lemma to show that $L=$ {$a^nb^kc^{n+k}:n\geq0,k\geq0$} is not regular.
Apply the pumping lemma to show that $L=$ {$a^nb^kc^{n+k}:n\geq0,k\geq0$} is not regular.
Naveen Kumar 3
242
views
Naveen Kumar 3
asked
Apr 11, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pumping-lemma
regular-language
+
–
2
votes
0
answers
159
Peter Linz Edition 4 Exercise 4.3 Question 10 (Page No. 123)
Consider the language $L=$ {$a^n:n$ is not a perfect square}. (a) Show that this language is not regular by applying the pumping lemma directly. (b) Then show the same thing by using the closure properties of regular languages.
Consider the language $L=$ {$a^n:n$ is not a perfect square}.(a) Show that this language is not regular by applying the pumping lemma directly.(b) Then show the same thin...
Naveen Kumar 3
240
views
Naveen Kumar 3
asked
Apr 11, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pumping-lemma
regular-language
closure-property
+
–
0
votes
1
answer
160
Peter Linz Edition 4 Exercise 4.3 Question 9 (Page No. 123)
Is the language $L=$ {$w∈$ {$a,b,c$}$^*$ $:|w|=3n_a(w)$} regular?
Is the language $L=$ {$w∈$ {$a,b,c$}$^*$ $:|w|=3n_a(w)$} regular?
Naveen Kumar 3
280
views
Naveen Kumar 3
asked
Apr 11, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pumping-lemma
regular-language
+
–
0
votes
1
answer
161
Peter Linz Edition 4 Exercise 4.3 Question 8 (Page No. 123)
Show that the language $L=$ {$a^nb^{n+k}:n\geq0,k\geq1$} $\cup$ {$a^{n+k}b^n:n\geq0,k\geq3$} is not regular.
Show that the language $L=$ {$a^nb^{n+k}:n\geq0,k\geq1$} $\cup$ {$a^{n+k}b^n:n\geq0,k\geq3$} is not regular.
Naveen Kumar 3
281
views
Naveen Kumar 3
asked
Apr 11, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pumping-lemma
regular-language
+
–
1
votes
0
answers
162
Peter Linz Edition 4 Exercise 4.3 Question 7 (Page No. 123)
Show that the language $L=$ {$a^nb^n:n\geq0$} $\cup$ {$a^nb^{n+1}:n\geq0$} $\cup$ {$a^nb^{n+2}:n\geq0$} is not regular.
Show that the language $L=$ {$a^nb^n:n\geq0$} $\cup$ {$a^nb^{n+1}:n\geq0$} $\cup$ {$a^nb^{n+2}:n\geq0$} is not regular.
Naveen Kumar 3
149
views
Naveen Kumar 3
asked
Apr 11, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pumping-lemma
+
–
1
votes
0
answers
163
Peter Linz Edition 4 Exercise 4.3 Question 5 (Page No. 122)
Determine whether or not the following languages on $Σ =$ {$a$} are regular. (a) $L =$ {$a^n: n ≥ 2,$ is a prime number}. (b) $L =$ {$a^n: n$ is not a prime number}. (c) $L =$ {$a^n: n = k^3$ for some $k ≥ 0$}. ( ... {$a^n: n$ is either prime or the product of two or more prime numbers}. (g) $L^*$, where $L$ is the language in part $(a)$.
Determine whether or not the following languages on $Σ =$ {$a$} are regular.(a) $L =$ {$a^n: n ≥ 2,$ is a prime number}.(b) $L =$ {$a^n: n$ is not a prime number}.(c) ...
Naveen Kumar 3
347
views
Naveen Kumar 3
asked
Apr 11, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pumping-lemma
regular-language
+
–
0
votes
0
answers
164
Peter Linz Edition 4 Exercise 4.3 Question 4 (Page No. 122)
Prove that the following languages are not regular. (a) $L =$ {$a^nb^la^k : k ≥ n + l$}. (b) $L =$ {$a^nb^la^k : k ≠ n + l$}. (c) $L =$ {$a^nb^la^k: n = l$ or $l ≠ k$}. (d) $L =$ {$a^nb^l : n ≤ l$}. (e) $L =$ {$w: n_a (w) ≠ n_b (w)$ }. (f) $L =$ {$ww : w ∈${$a, b$}$^*$}. (g) $L =$ {$wwww^R : w ∈$ {$a, b$}$^*$}.
Prove that the following languages are not regular.(a) $L =$ {$a^nb^la^k : k ≥ n + l$}.(b) $L =$ {$a^nb^la^k : k ≠ n + l$}.(c) $L =$ {$a^nb^la^k: n = l$ or $l ≠ k$}...
Naveen Kumar 3
218
views
Naveen Kumar 3
asked
Apr 11, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pumping-lemma
regular-language
+
–
0
votes
1
answer
165
Peter Linz Edition 4 Exercise 4.3 Question 3 (Page No. 122)
Show that the language $L = \{w : n_a (w) = n_b(w) \}$ is not regular. Is $L^*$ regular?
Show that the language $L = \{w : n_a (w) = n_b(w) \}$ is not regular. Is $L^*$ regular?
Naveen Kumar 3
327
views
Naveen Kumar 3
asked
Apr 11, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pumping-lemma
regular-language
+
–
0
votes
0
answers
166
Peter Linz Edition 4 Exercise 4.3 Question 2 (Page No. 122)
Prove the following generalization of the pumping lemma. If $L$ is regular, then there exists an $m$, such that the following holds for every sufficiently long $w ∈ L$ and every one of its decompositions $w = u_1υu_2$, with $u_1,u_2 ∈ Σ^*, |υ| \geq m.$ The ... $|xy| ≤ m, |y| ≥ 1,$ such that $u_1xy^izu_2 ∈ L$ for all $i = 0,1, 2, .$
Prove the following generalization of the pumping lemma.If $L$ is regular, then there exists an $m$, such that the following holds for every sufficiently long $w ∈ L$ a...
Naveen Kumar 3
137
views
Naveen Kumar 3
asked
Apr 11, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pumping-lemma
+
–
1
votes
1
answer
167
Peter Linz Edition 4 Exercise 4.3 Question 1 (Page No. 122)
Prove the following version of the pumping lemma. If $L$ is regular, then there is an $m$ such that, every $w ∈ L$ of length greater than $m$ can be decomposed as $w = xyz,$ with $|yz| ≤ m$ and $|y| ≥ 1,$ such that $xy^iz$ is in $L$ for all $i$.
Prove the following version of the pumping lemma. If $L$ is regular, then there is an $m$ such that,every $w ∈ L$ of length greater than $m$ can be decomposed as $w = x...
Naveen Kumar 3
253
views
Naveen Kumar 3
asked
Apr 11, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pumping-lemma
+
–
0
votes
0
answers
168
Peter Linz Edition 4 Exercise 4.2 Question 15 (Page No. 114)
Describe an algorithm which, when given a regular grammar $G$, can tell us whether or not $L (G) = Σ^*$.
Describe an algorithm which, when given a regular grammar $G$, can tell us whether or not $L (G) = Σ^*$.
Naveen Kumar 3
135
views
Naveen Kumar 3
asked
Apr 10, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
+
–
0
votes
1
answer
169
Peter Linz Edition 4 Exercise 4.2 Question 14 (Page No. 114)
Find an algorithm for determining whether a regular language $L$ contains an infinite number of even-length strings.
Find an algorithm for determining whether a regular language $L$ contains an infinite number of even-length strings.
Naveen Kumar 3
355
views
Naveen Kumar 3
asked
Apr 10, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
+
–
0
votes
0
answers
170
Peter Linz Edition 4 Exercise 4.2 Question 13 (Page No. 114)
Show that there exists an algorithm that can determine for every regular language $L$, whether or not $|L| ≥ 5$.
Show that there exists an algorithm that can determine for every regular language $L$, whether or not $|L| ≥ 5$.
Naveen Kumar 3
125
views
Naveen Kumar 3
asked
Apr 10, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
+
–
0
votes
0
answers
171
Peter Linz Edition 4 Exercise 4.2 Question 12 (Page No. 113)
Let $L$ be any regular language on $Σ =$ {$a, b$}. Show that an algorithm exists for determining if $L$ contains any strings of even length.
Let $L$ be any regular language on $Σ =$ {$a, b$}. Show that an algorithm exists for determining if $L$ contains any strings of even length.
Naveen Kumar 3
178
views
Naveen Kumar 3
asked
Apr 10, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
+
–
0
votes
0
answers
172
Peter Linz Edition 4 Exercise 4.2 Question 11 (Page No. 113)
The operation $tail (L)$ is defined as $tail(L)=$ {$v:uv∈L,u,v∈Σ^*$}. Show that there is an algorithm for determining whether or not $L = tail (L)$ for any regular $L$.
The operation $tail (L)$ is defined as $tail(L)=$ {$v:uv∈L,u,v∈Σ^*$}.Show that there is an algorithm for determining whether or not $L = tail (L)$ for any regular $L...
Naveen Kumar 3
128
views
Naveen Kumar 3
asked
Apr 10, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
+
–
0
votes
0
answers
173
Peter Linz Edition 4 Exercise 4.2 Question 10 (Page No. 113)
Show that there is an algorithm to determine if $L = shuffle (L, L)$ for any regular $L$.
Show that there is an algorithm to determine if $L = shuffle (L, L)$ for any regular $L$.
Naveen Kumar 3
170
views
Naveen Kumar 3
asked
Apr 10, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
+
–
0
votes
0
answers
174
Peter Linz Edition 4 Exercise 4.2 Question 9 (Page No. 113)
Let $L$ be a regular language on $Σ$ and $\widehat{w}$ be any string in $Σ^*$. Find an algorithm to determine if $L$ contains any $w$ such that $\widehat{w}$ is a substring of it, that is, such that $w = u\widehat{w} υ$ with $u,υ ∈Σ^*$ .
Let $L$ be a regular language on $Σ$ and $\widehat{w}$ be any string in $Σ^*$. Find an algorithm to determine if $L$ contains any $w$ such that $\widehat{w}$ is a subst...
Naveen Kumar 3
149
views
Naveen Kumar 3
asked
Apr 10, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
+
–
0
votes
0
answers
175
Peter Linz Edition 4 Exercise 4.2 Question 8 (Page No. 113)
Exhibit an algorithm that, given any regular language $L$, determines whether or not $L =L^*$.
Exhibit an algorithm that, given any regular language $L$, determines whether or not $L =L^*$.
Naveen Kumar 3
156
views
Naveen Kumar 3
asked
Apr 10, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
+
–
0
votes
0
answers
176
Peter Linz Edition 4 Exercise 4.2 Question 7 (Page No. 113)
Exhibit an algorithm that, given any three regular languages, $L, L_1, L_2,$ determines whether or not $L = L_1 L_ 2$.
Exhibit an algorithm that, given any three regular languages, $L, L_1, L_2,$ determines whether or not $L = L_1 L_ 2$.
Naveen Kumar 3
110
views
Naveen Kumar 3
asked
Apr 10, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
+
–
0
votes
0
answers
177
Peter Linz Edition 4 Exercise 4.2 Question 6 (Page No. 113)
Exhibit an algorithm for determining whether or not a regular language $L$ contains any string $w$ such that $w^ R ∈ L$.
Exhibit an algorithm for determining whether or not a regular language $L$ contains any string $w$ such that $w^ R ∈ L$.
Naveen Kumar 3
125
views
Naveen Kumar 3
asked
Apr 10, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
+
–
0
votes
1
answer
178
Peter Linz Edition 4 Exercise 4.2 Question 5 (Page No. 113)
A language is said to be a palindrome language if $L = L^R$. Find an algorithm for determining if a given regular language is a palindrome language.
A language is said to be a palindrome language if $L = L^R$. Find an algorithm for determining if agiven regular language is a palindrome language.
Naveen Kumar 3
441
views
Naveen Kumar 3
asked
Apr 10, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
+
–
0
votes
0
answers
179
Peter Linz Edition 4 Exercise 4.2 Question 4 (Page No. 113)
Show that for any regular $L_1$ and $L_2$ there is an algorithm to determine whether or not $L_1 = L_1/L_2$.
Show that for any regular $L_1$ and $L_2$ there is an algorithm to determine whether or not $L_1 = L_1/L_2$.
Naveen Kumar 3
118
views
Naveen Kumar 3
asked
Apr 10, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
+
–
0
votes
0
answers
180
Peter Linz Edition 4 Exercise 4.2 Question 3 (Page No. 113)
Show that there exists an algorithm for determining if $λ ∈ L$, for any regular language $L$.
Show that there exists an algorithm for determining if $λ ∈ L$, for any regular language $L$.
Naveen Kumar 3
129
views
Naveen Kumar 3
asked
Apr 10, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
+
–
Page:
« prev
1
2
3
4
5
6
7
8
9
10
11
...
13
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register