Dark Mode

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|$}

Naveen Kumar 3 asked in Theory of Computation Apr 12, 2019

by Naveen Kumar 3

108 views

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∈Σ^+$}.

Naveen Kumar 3 asked in Theory of Computation Apr 12, 2019

by Naveen Kumar 3

122 views

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?

Naveen Kumar 3 asked in Theory of Computation Apr 12, 2019

by Naveen Kumar 3

79 views

1 vote

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$}.

Naveen Kumar 3 asked in Theory of Computation Apr 12, 2019

by Naveen Kumar 3

205 views

0 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$}

Naveen Kumar 3 asked in Theory of Computation Apr 12, 2019

by Naveen Kumar 3

223 views

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$}.

Naveen Kumar 3 asked in Theory of Computation Apr 11, 2019

by Naveen Kumar 3

227 views

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.

Naveen Kumar 3 asked in Theory of Computation Apr 11, 2019

by Naveen Kumar 3

185 views

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.

Naveen Kumar 3 asked in Theory of Computation Apr 11, 2019

by Naveen Kumar 3

168 views

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.

Naveen Kumar 3 asked in Theory of Computation Apr 11, 2019

by Naveen Kumar 3

189 views

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?

Naveen Kumar 3 asked in Theory of Computation Apr 11, 2019

by Naveen Kumar 3

221 views

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.

Naveen Kumar 3 asked in Theory of Computation Apr 11, 2019

by Naveen Kumar 3

163 views

1 vote

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.

Naveen Kumar 3 asked in Theory of Computation Apr 11, 2019

by Naveen Kumar 3

103 views

1 vote

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)$.

Naveen Kumar 3 asked in Theory of Computation Apr 11, 2019

by Naveen Kumar 3

253 views

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$}$^*$}.

Naveen Kumar 3 asked in Theory of Computation Apr 11, 2019

by Naveen Kumar 3

138 views

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?

Naveen Kumar 3 asked in Theory of Computation Apr 11, 2019

by Naveen Kumar 3

227 views

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, .$

Naveen Kumar 3 asked in Theory of Computation Apr 11, 2019

by Naveen Kumar 3

102 views

0 votes

0 answers

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$.

Naveen Kumar 3 asked in Theory of Computation Apr 11, 2019

by Naveen Kumar 3

174 views

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) = Σ^*$.

Naveen Kumar 3 asked in Theory of Computation Apr 10, 2019

by Naveen Kumar 3

80 views

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.

Naveen Kumar 3 asked in Theory of Computation Apr 10, 2019

by Naveen Kumar 3

203 views

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$.

Naveen Kumar 3 asked in Theory of Computation Apr 10, 2019

by Naveen Kumar 3

88 views

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.

Naveen Kumar 3 asked in Theory of Computation Apr 10, 2019

by Naveen Kumar 3

126 views

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$.

Naveen Kumar 3 asked in Theory of Computation Apr 10, 2019

by Naveen Kumar 3

85 views

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$.

Naveen Kumar 3 asked in Theory of Computation Apr 10, 2019

by Naveen Kumar 3

107 views

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,υ ∈Σ^*$ .

Naveen Kumar 3 asked in Theory of Computation Apr 10, 2019

by Naveen Kumar 3

108 views

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^*$.

Naveen Kumar 3 asked in Theory of Computation Apr 10, 2019

by Naveen Kumar 3

106 views

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$.

Naveen Kumar 3 asked in Theory of Computation Apr 10, 2019

by Naveen Kumar 3

68 views

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$.

Naveen Kumar 3 asked in Theory of Computation Apr 10, 2019

by Naveen Kumar 3

88 views

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.

Naveen Kumar 3 asked in Theory of Computation Apr 10, 2019

by Naveen Kumar 3

215 views

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$.

Naveen Kumar 3 asked in Theory of Computation Apr 10, 2019

by Naveen Kumar 3

61 views

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$.

Naveen Kumar 3 asked in Theory of Computation Apr 10, 2019

by Naveen Kumar 3

81 views

Page:

« prev
1
2
3
4
5
6
7
8
9
10
11
...
13
next »

Recent questions tagged peter-linz-edition4