gaurangsaini / sipser-computation-3rd-solutions Goto Github PK

Question 1.54

1. (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

2. (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

Hello,
I think yellow ones are supposed to be the accept states,

And the complement of that is should be like this.

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!)

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
$\forall \omega \in HALT \iff f(\omega) \in T$
Let's define

$HALT$ to be

$$ HALT = { \langle x, y \rangle \in \Sigma^{*} \times \Sigma^{*}: x = code(M),M \text{ halts on } x} $$

Now we set $f$ as follows:

if $x \neq code(\mathcal{M}) \forall \mathcal{M}$ then we return $x$, which clearly is not in $T$
Else we return the machine $N$ as defined:

1. With input $z$ ignore the input.
2. Simulate $x$ on input $y$.
3. If $x$ halts then accept the input.
4. Else continue to loop with $x$.

We see that $\langle x, y \rangle \in HALT \iff N \in T$

Now, if we can decide the language $T$ we would able to decide $HALT$, which is absurd.

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.

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)

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.

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.

I don't think that the function you builded in the solution is computable. (can't decide wheter x is in A or not)

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

go fuck yourself please!!!

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.