Recent questions tagged peter-linz / GATE Overflow for GATE CSE

0 votes

1 answer

181

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

261 views

Naveen Kumar 3 asked Apr 11, 2019

2 votes

0 answers

182

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

242 views

Naveen Kumar 3 asked Apr 11, 2019

0 votes

1 answer

183

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

287 views

Naveen Kumar 3 asked Apr 11, 2019

0 votes

1 answer

184

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

287 views

Naveen Kumar 3 asked Apr 11, 2019

1 votes

0 answers

185

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

151 views

Naveen Kumar 3 asked Apr 11, 2019

1 votes

0 answers

186

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

362 views

Naveen Kumar 3 asked Apr 11, 2019

0 votes

0 answers

187

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

220 views

Naveen Kumar 3 asked Apr 11, 2019

0 votes

1 answer

188

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

340 views

Naveen Kumar 3 asked Apr 11, 2019

0 votes

0 answers

189

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

143 views

Naveen Kumar 3 asked Apr 11, 2019

1 votes

1 answer

190

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

259 views

Naveen Kumar 3 asked Apr 11, 2019

0 votes

0 answers

191

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

144 views

Naveen Kumar 3 asked Apr 10, 2019

0 votes

1 answer

192

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

369 views

Naveen Kumar 3 asked Apr 10, 2019

0 votes

0 answers

193

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

126 views

Naveen Kumar 3 asked Apr 10, 2019

0 votes

0 answers

194

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

182 views

Naveen Kumar 3 asked Apr 10, 2019

0 votes

0 answers

195

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

131 views

Naveen Kumar 3 asked Apr 10, 2019

0 votes

0 answers

196

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

175 views

Naveen Kumar 3 asked Apr 10, 2019

0 votes

0 answers

197

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

150 views

Naveen Kumar 3 asked Apr 10, 2019

0 votes

0 answers

198

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

162 views

Naveen Kumar 3 asked Apr 10, 2019

0 votes

0 answers

199

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

112 views

Naveen Kumar 3 asked Apr 10, 2019

0 votes

0 answers

200

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

127 views

Naveen Kumar 3 asked Apr 10, 2019

0 votes

1 answer

201

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

453 views

Naveen Kumar 3 asked Apr 10, 2019

0 votes

0 answers

202

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

122 views

Naveen Kumar 3 asked Apr 10, 2019

0 votes

0 answers

203

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

136 views

Naveen Kumar 3 asked Apr 10, 2019

0 votes

0 answers

204

Peter Linz Edition 4 Exercise 4.2 Question 2 (Page No. 113)
Show that there exists an algorithm for determining if $L_1 ⊆ L_2$, for any regular languages $L_1$ and $L_2$.

Show that there exists an algorithm for determining if $L_1 ⊆ L_2$, for any regular languages $L_1$ and $L_2$.

Naveen Kumar 3

167 views

Naveen Kumar 3 asked Apr 10, 2019

0 votes

0 answers

205

Peter Linz Edition 4 Exercise 4.2 Question 1 (Page No. 113)
Show that there exists an algorithm to determine whether or not $w ∈ L_1 − L_2$, for any given $w$ and any regular languages $L_1$ and $L_2$.

Show that there exists an algorithm to determine whether or not $w ∈ L_1 − L_2$, for any given $w$ andany regular languages $L_1$ and $L_2$.

Naveen Kumar 3

259 views

Naveen Kumar 3 asked Apr 10, 2019

0 votes

0 answers

206

Peter Linz Edition 5 Exercise 9.3 Question 1 (Page No. 248)
Consider the set of machine language instructions for a computer of your choice. Sketch how the various instructions in this set could be carried out by a Turing machine.

Consider the set of machine language instructions for a computer of your choice. Sketch how the various instructions in this set could be carried out by a Turing machine....

Rishi yadav

197 views

Rishi yadav asked Apr 9, 2019

0 votes

0 answers

207

Peter Linz Edition 5 Exercise 9.2 Question 8,9,10 (Page No. 245)
$\text{Exercise 8}:$ Give an implementation of the macroinstruction $\text{searchright} (a,q_i,q_j),$ ... $a$ by a blank. If the input contains no $a$, replace the rightmost nonblank symbol by a $b.$

$\text{Exercise 8}:$ Give an implementation of the macroinstruction $\text{searchright} (a,q_i,q_j...

Rishi yadav

389 views

Rishi yadav asked Apr 9, 2019

0 votes

0 answers

208

Peter Linz Edition 5 Exercise 9.2 Question 7 (Page No. 245)
Sketch the construction of a Turing machine that can perform the addition and multiplication of positive integers $x$ and $y$ given in the usual decimal notation.

Sketch the construction of a Turing machine that can perform the addition and multiplication of positive integers $x$ and $y$ given in the usual decimal notation.

Rishi yadav

175 views

Rishi yadav asked Apr 9, 2019

0 votes

0 answers

209

Peter Linz Edition 5 Exercise 9.2 Question 6 (Page No. 245)
Suggest a method for representing rational numbers on a Turing machine, then sketch a method for adding and subtracting such numbers.

Suggest a method for representing rational numbers on a Turing machine, then sketch a method for adding and subtracting such numbers.

Rishi yadav

242 views

Rishi yadav asked Apr 9, 2019

0 votes

0 answers

210

Peter Linz Edition 5 Exercise 9.2 Question 5(e) (Page No. 245)
Provide a “high-level” description for Turing machines that accept the following languages on $\{a,b\}.$ For each problem, define a set of appropriate macroinstructions that you feel are reasonably easy to implement. Then use them for the solution. $L = \{a^n : n\text{ is a prime number}\}.$

Provide a “high-level” description for Turing machines that accept the following languages on $\{a,b\}.$ For each problem, define a set of appropriate macroinstructio...

Rishi yadav

215 views

Rishi yadav asked Apr 9, 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