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

0 votes

0 answers

1

Peter Linz Edition 5 Exercise 10.5 Question 3
Consider an offline Turing machine in which the input can be read only once, moving left to right, and not rewritten. On its work tape, it can use at most n extra cells for work space, where n is fixed for all inputs. Show that such a machine is equivalent to a finite automaton.

Consider an offline Turing machine in which the input can be read only once, moving left to right, and not rewritten. On its work tape, it can use at most n extra cells f...

borhanElmi

321 views

borhanElmi asked Feb 8, 2023

0 votes

0 answers

2

Peter Linz Edition 5 Exercise 2.2 Question 7 (Page No. 79)
Design an nfa with no more than five states for the set $\left \{ abab^n: n >0 \right \} \cup \left \{ ab{a}^n : n\geq 0 \right \}$

Design an nfa with no more than five states for the set $\left \{ abab^n: n >0 \right \} \cup \left \{ ab{a}^n : n\geq 0 \right \}$

ankit-saha

408 views

ankit-saha asked Mar 19, 2022

0 votes

0 answers

3

Peter Linz Edition 5 Exercise 8.1 Question 7(k) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free $L = \{a^nb^m: \text{n is prime and m is not prime}\}$.

Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free $L = \{a^nb^m: \text{n is prime and m is not ...

Rishi yadav

368 views

Rishi yadav asked Apr 15, 2019

0 votes

1 answer

4

Peter Linz Edition 5 Exercise 8.1 Question 7(j) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free $L = \{a^nb^m:\text{n is prime or m is prime}\}$.

Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free $L = \{a^nb^m:\text{n is prime or m is prim...

Rishi yadav

354 views

Rishi yadav asked Apr 15, 2019

0 votes

0 answers

5

Peter Linz Edition 5 Exercise 8.1 Question 7(i) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free $L = \{a^nb^m: \text{n and m are both prime}\}$.

Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free $L = \{a^nb^m: \text{n and m are both prim...

Rishi yadav

197 views

Rishi yadav asked Apr 15, 2019

0 votes

0 answers

6

Peter Linz Edition 5 Exercise 8.1 Question 7(h) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L = \{w\in\{a,b,c\}^*:n_a(w)+n_b(w)=2n_c(w),n_a(w) = n_b(w)\}$.

Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L = \{w\in\{a,b,c\}^*:n_a(w)+n_b(w)=2n_c(w),n_a(w) = n_b(w)\...

Rishi yadav

297 views

Rishi yadav asked Apr 15, 2019

0 votes

0 answers

7

Peter Linz Edition 5 Exercise 8.1 Question 7(g) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L=\{w:n_a(w)/n_b(w) = n_c(w)\}$.

Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L=\{w:n_a(w)/n_b(w) = n_c(w...

Rishi yadav

179 views

Rishi yadav asked Apr 15, 2019

0 votes

0 answers

8

Peter Linz Edition 5 Exercise 8.1 Question 7(f) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L = \{w:n_a(w) <n_b(w)<n_c(w)\}$.

Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $$L = \{w:n_a(w) <n_b(w)<n_c(w)\}$$.

Rishi yadav

225 views

Rishi yadav asked Apr 15, 2019

0 votes

0 answers

9

Peter Linz Edition 5 Exercise 8.1 Question 7(e) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L= \{a^nb^jc^k:n<j,n\leq k \leq j\}$.

Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L= \{a^nb^jc^k:n<j,n\leq k \leq j\}$...

Rishi yadav

284 views

Rishi yadav asked Apr 15, 2019

0 votes

0 answers

10

Peter Linz Edition 5 Exercise 8.1 Question 7(d) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L=\{a^nb^jc^k : k>n,k>j\}$.

Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L=\{a^nb^jc^k : k>n,k>j\}$.

Rishi yadav

195 views

Rishi yadav asked Apr 15, 2019

0 votes

2 answers

11

Peter Linz Edition 5 Exercise 8.1 Question 7(c) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L = \{a^nb^jc^k:k=jn\}$.

Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L = \{a^nb^jc^k:k=jn\...

Rishi yadav

518 views

Rishi yadav asked Apr 15, 2019

0 votes

0 answers

12

Peter Linz Edition 5 Exercise 8.1 Question 7(b) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L = \{a^nb^j: n\geq(j-1)^3\}$.

Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L = \{a^nb^j: n\geq(j-...

Rishi yadav

145 views

Rishi yadav asked Apr 15, 2019

1 votes

0 answers

13

Peter Linz Edition 5 Exercise 8.1 Question 7(a) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L = \{a^nb^j : n\leq j^2\}$.

Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L = \{a^nb^j : n\leq j^2\}...

Rishi yadav

285 views

Rishi yadav asked Apr 15, 2019

0 votes

0 answers

14

Peter Linz Edition 5 Exercise 8.1 Question 6 (Page No. 212)
Show that the language $L = \Big\{ a^{n^2} :n\geq 0\Big\}$ is not context free.

Show that the language $L = \Big\{ a^{n^2} :n\geq 0\Big\}$ is not context free.

Rishi yadav

314 views

Rishi yadav asked Apr 15, 2019

0 votes

0 answers

15

Peter Linz Edition 5 Exercise 8.1 Question 5 (Page No. 212)
Is the language $L = \{a^nb^m:n=2^m\}$ context free$?$

Is the language $L = \{a^nb^m:n=2^m\}$ context free$?$

Rishi yadav

241 views

Rishi yadav asked Apr 15, 2019

0 votes

0 answers

16

Peter Linz Edition 5 Exercise 8.1 Question 4 (Page No. 212)
Show that $L=\{w \in \{a,b,c\}^*:n_a^2(w) + n_b^2(w) = n_c^2(w)\}$ is not a context-free.

Show that $L=\{w \in \{a,b,c\}^*:n_a^2(w) + n_b^2(w) = n_c^2(w)\}$ is not a context-free.

Rishi yadav

155 views

Rishi yadav asked Apr 15, 2019

0 votes

0 answers

17

Peter Linz Edition 5 Exercise 8.1 Question 3 (Page No. 212)
Show that $L=\{ww^Rw:w\in\{a,b\}^*\}$ is not a context-free language.

Show that $L=\{ww^Rw:w\in\{a,b\}^*\}$ is not a context-free language.

Rishi yadav

192 views

Rishi yadav asked Apr 15, 2019

0 votes

0 answers

18

Peter Linz Edition 5 Exercise 8.1 Question 2 (Page No. 212)
Show that the language $L = \{a^n : n \text{ is a prime number}\}$ is not context-free.

Show that the language $L = \{a^n : n \text{ is a prime number}\}$ is not context-free.

Rishi yadav

141 views

Rishi yadav asked Apr 15, 2019

0 votes

0 answers

19

Peter Linz Edition 5 Exercise 8.1 Question 1 (Page No. 212)
Show that the language $L = \{w\in \{a,b,c\}^*: n_a(w) = n_b(w) \leq n_c(w)\}$ is not context-free.

Show that the language $L = \{w\in \{a,b,c\}^*: n_a(w) = n_b(w) \leq n_c(w)\}$is not context-free.

Rishi yadav

145 views

Rishi yadav asked Apr 15, 2019

0 votes

0 answers

20

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

201 views

Rishi yadav asked Apr 9, 2019

0 votes

0 answers

21

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

391 views

Rishi yadav asked Apr 9, 2019

0 votes

0 answers

22

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

180 views

Rishi yadav asked Apr 9, 2019

0 votes

0 answers

23

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

251 views

Rishi yadav asked Apr 9, 2019

0 votes

0 answers

24

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

220 views

Rishi yadav asked Apr 9, 2019

0 votes

0 answers

25

Peter Linz Edition 5 Exercise 9.2 Question 5(d) (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^nb^m : m = n^2,n\geq1\}.$

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

165 views

Rishi yadav asked Apr 9, 2019

0 votes

0 answers

26

Peter Linz Edition 5 Exercise 9.2 Question 5(c) (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. $\text{The complement of the language in }L = \{ww^R\}.$

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

224 views

Rishi yadav asked Apr 9, 2019

0 votes

0 answers

27

Peter Linz Edition 5 Exercise 9.2 Question 5(b) (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 = \{w_1w_2: w_1 \neq w_2: |w_1| = |w_2|\}.$

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

119 views

Rishi yadav asked Apr 9, 2019

0 votes

0 answers

28

Peter Linz Edition 5 Exercise 9.2 Question 5(a) (Page No. 244)
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 = \{ww^R\}.$

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

199 views

Rishi yadav asked Apr 9, 2019

0 votes

0 answers

29

Peter Linz Edition 5 Exercise 9.2 Question 4 (Page No. 244)
Use a block diagram to sketch the implementation of a function f defined for all $w_1,w_2,w_3\in \{1\}^+$ by $f(w_1,w_2,w_3) = i,$ where $i$ is such that $|w_i| = \text{max}(|w_1|,|w_2|,|w_3|)$ if no two $w’s$ have the same length, and $i=0$ otherwise.

Use a block diagram to sketch the implementation of a function f defined for all $w_1,w_2,w_3\in \{1\}^+$ by ...

Rishi yadav

143 views

Rishi yadav asked Apr 9, 2019

0 votes

0 answers

30

Peter Linz Edition 5 Exercise 9.2 Question 3(d) (Page No. 244)
Using adders, subtracters, comparers, copies or multipliers, draw block diagrams for Turing machines that compute the functions for all positive integers $n$ $f(n) = n!,$

Using adders, subtracters, comparers, copies or multipliers, draw block diagrams for Turing machines that compute the functions for all positive integers $n$ ...

Rishi yadav

275 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