Login
Register
@
Dark Mode
Profile
Edit my Profile
Messages
My favorites
Register
Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous Years
Blogs
New Blog
Exams
Dark Mode
Recent questions tagged peter-linz-edition5
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.
borhanElmi
asked
in
Theory of Computation
Feb 8, 2023
by
borhanElmi
314
views
theory-of-computation
peter-linz-edition5
turing-machine
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 \}$
ankit-saha
asked
in
Theory of Computation
Mar 19, 2022
by
ankit-saha
380
views
peter-linz
theory-of-computation
peter-linz-edition5
finite-automata
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}\}$.
Rishi yadav
asked
in
Theory of Computation
Apr 15, 2019
by
Rishi yadav
355
views
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
proof
context-free-language
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}\}$.
Rishi yadav
asked
in
Theory of Computation
Apr 15, 2019
by
Rishi yadav
343
views
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
proof
context-free-language
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}\}$.
Rishi yadav
asked
in
Theory of Computation
Apr 15, 2019
by
Rishi yadav
194
views
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
proof
context-free-language
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)\}$.
Rishi yadav
asked
in
Theory of Computation
Apr 15, 2019
by
Rishi yadav
292
views
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
proof
context-free-language
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)\}$.
Rishi yadav
asked
in
Theory of Computation
Apr 15, 2019
by
Rishi yadav
174
views
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
proof
context-free-language
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)\}$.
Rishi yadav
asked
in
Theory of Computation
Apr 15, 2019
by
Rishi yadav
222
views
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
proof
context-free-language
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\}$.
Rishi yadav
asked
in
Theory of Computation
Apr 15, 2019
by
Rishi yadav
275
views
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
proof
context-free-language
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\}$.
Rishi yadav
asked
in
Theory of Computation
Apr 15, 2019
by
Rishi yadav
188
views
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
proof
context-free-language
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\}$.
Rishi yadav
asked
in
Theory of Computation
Apr 15, 2019
by
Rishi yadav
457
views
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
proof
context-free-language
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\}$.
Rishi yadav
asked
in
Theory of Computation
Apr 15, 2019
by
Rishi yadav
145
views
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
proof
context-free-language
1
vote
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\}$.
Rishi yadav
asked
in
Theory of Computation
Apr 15, 2019
by
Rishi yadav
280
views
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
proof
context-free-language
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.
Rishi yadav
asked
in
Theory of Computation
Apr 15, 2019
by
Rishi yadav
302
views
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
proof
context-free-language
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$?$
Rishi yadav
asked
in
Theory of Computation
Apr 15, 2019
by
Rishi yadav
242
views
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
context-free-language
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.
Rishi yadav
asked
in
Theory of Computation
Apr 15, 2019
by
Rishi yadav
149
views
peter-linz
peter-linz-edition5
theory-of-computation
proof
pumping-lemma
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.
Rishi yadav
asked
in
Theory of Computation
Apr 15, 2019
by
Rishi yadav
181
views
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
proof
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.
Rishi yadav
asked
in
Theory of Computation
Apr 15, 2019
by
Rishi yadav
131
views
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
proof
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.
Rishi yadav
asked
in
Theory of Computation
Apr 15, 2019
by
Rishi yadav
145
views
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
proof
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.
Rishi yadav
asked
in
Theory of Computation
Apr 9, 2019
by
Rishi yadav
198
views
peter-linz
peter-linz-edition5
theory-of-computation
turing-machine
difficult
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.$
Rishi yadav
asked
in
Theory of Computation
Apr 9, 2019
by
Rishi yadav
390
views
peter-linz
peter-linz-edition5
theory-of-computation
turing-machine
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.
Rishi yadav
asked
in
Theory of Computation
Apr 9, 2019
by
Rishi yadav
176
views
peter-linz
peter-linz-edition5
theory-of-computation
turing-machine
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.
Rishi yadav
asked
in
Theory of Computation
Apr 9, 2019
by
Rishi yadav
233
views
peter-linz
peter-linz-edition5
theory-of-computation
turing-machine
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}\}.$
Rishi yadav
asked
in
Theory of Computation
Apr 9, 2019
by
Rishi yadav
213
views
peter-linz
peter-linz-edition5
theory-of-computation
turing-machine
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\}.$
Rishi yadav
asked
in
Theory of Computation
Apr 9, 2019
by
Rishi yadav
155
views
peter-linz
peter-linz-edition5
theory-of-computation
turing-machine
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\}.$
Rishi yadav
asked
in
Theory of Computation
Apr 9, 2019
by
Rishi yadav
218
views
peter-linz
peter-linz-edition5
theory-of-computation
turing-machine
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|\}.$
Rishi yadav
asked
in
Theory of Computation
Apr 9, 2019
by
Rishi yadav
112
views
peter-linz
peter-linz-edition5
theory-of-computation
turing-machine
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\}.$
Rishi yadav
asked
in
Theory of Computation
Apr 9, 2019
by
Rishi yadav
191
views
peter-linz
peter-linz-edition5
theory-of-computation
turing-machine
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.
Rishi yadav
asked
in
Theory of Computation
Apr 9, 2019
by
Rishi yadav
138
views
peter-linz
peter-linz-edition5
theory-of-computation
turing-machine
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!,$
Rishi yadav
asked
in
Theory of Computation
Apr 9, 2019
by
Rishi yadav
269
views
peter-linz
peter-linz-edition5
theory-of-computation
turing-machine
Page:
1
2
3
4
5
6
7
next »
Subscribe to GATE CSE 2024 Test Series
Subscribe to GO Classes for GATE CSE 2024
Quick search syntax
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
Recent Posts
Post GATE 2024 Guidance [Counseling tips and resources]
GATE CSE 2024 Result Responses
[Project Contest] Pytorch backend support for MLCommons Cpp Inference implementation
Participating in MLCommons Inference v4.0 submission (deadline is February 23 12pm IST)
IIITH PGEE 2024 Test Series by GO Classes
Subjects
All categories
General Aptitude
(3.5k)
Engineering Mathematics
(10.4k)
Digital Logic
(3.6k)
Programming and DS
(6.2k)
Algorithms
(4.8k)
Theory of Computation
(6.9k)
Compiler Design
(2.5k)
Operating System
(5.2k)
Databases
(4.8k)
CO and Architecture
(4.0k)
Computer Networks
(4.9k)
Artificial Intelligence
(79)
Machine Learning
(48)
Data Mining and Warehousing
(25)
Non GATE
(1.4k)
Others
(2.7k)
Admissions
(684)
Exam Queries
(1.6k)
Tier 1 Placement Questions
(17)
Job Queries
(80)
Projects
(11)
Unknown Category
(870)
64.3k
questions
77.9k
answers
244k
comments
80.0k
users
Recent questions tagged peter-linz-edition5
Recent Blog Comments
category ?
Hi @Arjun sir, I have obtained a score of 591 in ...
download here
Can you please tell about IIT-H mtech CSE self...
Please add your admission queries here:...