Computation & complexity

Track parity and whether the last symbol is zero. Some combinations may have identical future behavior even when their histories differ.

Three states suffice: E means even parity but not currently accepting (including the empty string); Z means even parity and last symbol zero; O means odd parity, regardless of the last symbol. Only Z accepts. On 0, E→Z, Z→Z, O→O. On 1, E→O, Z→O, O→E. Odd parity makes the current ending symbol irrelevant: both odd histories reject now and have identical transitions.

All states are reachable: ε reaches E, 0 reaches Z, and 1 reaches O. E and Z are distinguished by the empty suffix, as are O and Z. E and O are distinguished by suffix 0: E reaches accepting Z while O stays rejecting O. Therefore no two of these three reachable states can be merged, and three is minimal. An exhaustive check visits 1+2+4+8+16=31 strings; accept exactly those with positive length, final character 0, and count(1) even. Testing supports the implementation; the state invariant and distinguishing suffixes establish the general claim.

Check your reasoning

• Handle the empty string.
• Give every transition.
• Supply reachable states and distinguishing suffixes.

After the first 1, forbid any further 0. For the pumping proof choose a string only after the alleged pumping length is fixed.

Push one marker per 0. On the first 1, switch permanently to a popping phase and pop one marker per 1. Reject if a 1 needs a marker that is absent, or a 0 appears in the popping phase. Accept at end exactly when no markers remain; accept ε separately. Thus 0101 fails at its second 0, and 001 finishes with a marker left.

Assume a DFA exists. The pumping lemma gives p such that every sufficiently long accepted string has some decomposition xyz with |xy|≤p, |y|>0, and xyⁱz in L for every i≥0. Choose 0ᵖ1ᵖ. Every permitted y consists of one or more 0s. Pumping i=0 leaves fewer 0s than 1s, contradicting membership. The proof works for every permitted decomposition, not just one convenient split. A nondeterministic pushdown automaton with finite control, one stack, and one-way read-only input recognizes exactly the context-free languages. The recognizer for {0ⁿ1ⁿ} above is deterministic, but deterministic pushdown automata recognize a smaller class than all context-free languages. Even the nondeterministic model has a strict restriction: {0ⁿ1ⁿ2ⁿ} is decidable but not context-free. Its non-context-freeness requires a separate argument, such as the context-free pumping lemma; the regular pumping proof above does not prove that stronger result.

Check your reasoning

• Specify phase transitions and end-of-input behavior.
• Respect the for-every decomposition step.
• Do not apply the regular pumping lemma to context-free languages.

The construction must be computable without solving halting. A recognizer may run forever on a negative instance.

If H(D,D) predicts termination, D loops by construction. If it predicts looping, D terminates. Both cases contradict correctness, so no such total computable H exists for the general model. This does not say that termination cannot be proved for any particular program or restricted language.

Given P,x, construct Q that simulates P(x) while suppressing its output, then prints READY only after the simulation terminates. This syntactic construction is effective. If P(x) halts, Q prints READY; if P(x) does not halt, Q never reaches the print. A hypothetical READY decider would therefore decide halting. READY is recognizable: simulate the given program and accept when the designated output occurs. Its complement is not recognizable in this model. If both a property and its complement had recognizers, interleaving their steps would eventually obtain acceptance from exactly one and give a total decider. The argument assumes an unbounded abstract machine and a precise output event, not a finite physical machine with a fixed execution deadline.

Check your reasoning

• Show both branches of the diagonal contradiction.
• Build Q without calling a halting oracle.
• Distinguish recognition from a total decision procedure.

A reduction A≤pB means a solver for B gives a solver for A. To establish B as hard, start from a problem A already known to be hard.

A certificate lists k distinct vertex identifiers. Check that 0≤k≤|V|, identifiers belong to V, no duplicates occur, and every pair has an edge. With an adjacency matrix this uses O(k²) edge tests and polynomial total time; representation construction must also be counted if needed. The complement graph has the same vertices and an edge precisely between distinct vertices not adjacent in G. A set is a clique in G iff it has no pairwise edges in the complement, so it is an independent set of size k there. Building the complement takes O(|V|²) time with this representation.

The displayed reduction establishes that INDEPENDENT SET is at least as hard as CLIQUE. Hardness of the target alone does not establish hardness of the source: an easy problem can reduce to a hard one. Here the complement construction also works in the reverse direction, but that additional argument must be stated. Verification checks a supplied witness; trying all candidate subsets can take exponential time. P⊆NP is known; whether P=NP remains unresolved. NP-completeness combines membership in NP with reductions from all NP problems, often obtained through one already-established NP-complete source.

Check your reasoning

• Validate certificate format as well as edges.
• Prove the iff and polynomial construction.
• Use the reduction direction correctly and preserve the open status of P versus NP.