gaurangsaini / sipser-computation-3rd-solutions Goto Github PK
View Code? Open in Web Editor NEWSolutions to all questions of the book Introduction to the Theory of Computation, 3rd edition by Michael Sipser
Solutions to all questions of the book Introduction to the Theory of Computation, 3rd edition by Michael Sipser
The final state on the right in the image has no 1 transition. The 0 transition for that state should be 0 and 1 instead of just 0. For example consider the computation of 1111 with your current diagram to see the issue I'm talking about.
From: https://github.com/gaurangsaini/sipser-computation-3rd-solutions/blob/master/Chapter%201/6.pdf
I think the last rule should include ε, to make T -> 0|1|ε. This is because the original grammar does not generate "01#10" nor "10#01" which is described by the language. Adding the ε to T will allow for the grammer to generate these two strings.
The statement requires us to show that a language is decidable if and only if an enumerator enumerates it in the standard string order, but in the proof there is lexicographic order.
The standard string order means first to compare the length of the two strings and then compare character by character, but lexicographic string order means only compare the two strings character by character.
And there is a hack: a*b is a regular language and it is Turing decidable, but it cannot be enumerated by lexicographic order (and can be enumerated by the standard string order).
Proof of 3.19 and 3.17 uses the statement of 3.18, so it is wrong, too.
what if you have no node of only one edge incident on it? the proof is hence not inclusive of all possibilities and has no ability to decide whether all graphs with 2 nodes or more must have at least 2 nodes that are of equal degree.
In defining computations for finite state transducers the transition function is currently defined with the formula \delta(q_{i+1},w_{i+1})=(q_{i+1},x_{i+1}), this formula should be \delta(q_{i},w_{i+1})=(q_{i+1},x_{i+1}) because the transition function of an FST needs to tell you at a state q_i, on an input w_{i+1} where to transition to for the next state (which would be q_{i+1}) and what symbol to output (which would be x_{i+1}). (Sorry for the awkward pseudo-latex notation here!)
(Step 1 of 4) It is stated that the Language F is the union of three disjoint languages F0, F1, F2
but the string aabbbccc
is in F but in neither of F0,F1 or F2
(Step 2 of 4) To prove that the string a b^p c^p
can't be pumped, you have to check another case where u
is an empty string and v = a and z = b^p c^p
go fuck yourself please!!!
At "Assume x=0^(p-k),y=0^k", this is not a reasonable assumption to make. The pumping lemma tells you |xy|<=p, but you do not know necessarily that |xy|=p like in the assumption shown above.
Notice also at the line claiming xz=0^(p-k)10^p is not an element of L, we cannot actually conclude xz is not an element of L by this logic. Pick w=0, and pick t to be all but the first and last digit of xz (which must contain at least the digit 1), it follows xz=wtw so xz is still an element of L. This can be done any time p>k.
I think that there is no integer n such that n = n +1
By this, I think that Espsylon should be added as a comment to the actual solution.
Where was this solution sourced from?
It mixes Turing-reducibility with mapping-reducibility, fails to form a valid contradiction in the end, and makes logic mistakes (e.g. choosing a fixed A when the problem asks for every A)
Consider the machine that accepts everything. Clearly this machine is in the language T.
Now we mapping reduce from HALT to L using that machine. We need to prove that
Let's define
Now we set
if
Else we return the machine
We see that
Now, if we can decide the language
I don't think that the function you builded in the solution is computable. (can't decide wheter x is in A or not)
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.