Register

Recent questions tagged peter-linz-edition5

0 votes
0 answers
66
Peter Linz Edition 5 Exercise 9.1 Question 2 (Page No. 238)
Design a Turing machine with no more than three states that accept the language $L(a(a+b)^*)$. Assume that $\Sigma = \{a,b\}$. Is it possible to do this with a two-state machine$?$
Design a Turing machine with no more than three states that accept the language $L(a(a+b)^*)$. Assume that $\Sigma = \{a,b\}$. Is it possible to do this with a two-state ...
User Avatar
0 votes
0 answers
68
Peter Linz Edition 5 Exercise 10.5 Question 6,7 (Page No. 276)
$\text{Exercise}:6$ ... above exercise to show that any context-free language not containing $\lambda$ is accepted by some linear bounded automaton.
$\text{Exercise}:6$ Show that for every context-free language there exists an accepting pda, such that the number of symbols in the stack never exceeds the length of the...
User Avatar
0 votes
0 answers
83
Peter Linz Edition 5 Exercise 10.4 Question 4 (Page No. 272)
$\text{Exercise 3:}$ Sketch a Turing machine program that enumerates the set {0,1}+{0,1}+ in proper order. $\text{Exercise 4:}$ What is the index of $0^i1^j$ in Exercise 3$?$
$\text{Exercise 3:}$ Sketch a Turing machine program that enumerates the set {0,1}+{0,1}+ in proper order.$\text{Exercise 4:}$ What is the index of $0^i1^j$ in Exercise 3...
User Avatar
Page: