Convert to minimization with and retain . A continuously differentiable inequality augmented Lagrangian method uses the merit function
For its contribution is ; otherwise it is the constant . This shifted truncation permits multipliers to decrease as well as increase while remaining nonnegative.
A useful initial estimate comes from the preceding pure quadratic penalty method at :
Here , so with choose
Then use this estimate and in the first augmented subproblem. Initial estimates are a choice, rather than uniquely specified data; zero multipliers would also define an initialization.
Write , . The two inactive constraints are strict exactly for . Complementary slackness gives . The KKT conditions reduce to
If these give . Otherwise and , which gives a negative multiplier and is inadmissible. Therefore
is the only KKT point with this active set. Its active gradient is nonzero, so the linear independence constraint qualification, and hence the Mangasarian–Fromovitz constraint qualification, holds.
It is not a local maximizer: is feasible for small and has objective . The feasible boundary path for small negative has objective , so it is not a local minimizer either.
All three active constraints force and , which also satisfy . For maximization use , . At ,
Stationarity gives the complete family
In particular is strictly positive. Three gradients in two dimensions cannot be linearly independent, so the linear independence constraint qualification fails. But gives , so the Mangasarian–Fromovitz constraint qualification holds.
For a nonzero linearized feasible direction , each , and
The inequality is strict because equality would require all three inner products to vanish, and the first and third gradients already span . This proves a strict local maximum: otherwise a sequence of nearby feasible points with no smaller objective would, after normalizing their differences from and taking a convergent subsequence, give a unit linearized feasible direction with nonnegative objective derivative, contradicting the displayed inequality. Thus
Use for the maximized objective function, and adopt optimization constraints with
The feasible set is nonempty, since it contains . It is closed as an intersection of inverse images of closed sets under continuous functions. It lies in the disk of radius , so is bounded and therefore compact by the Heine-Borel theorem. The objective function is a polynomial, hence continuous. The extreme value theorem now guarantees a global maximizer exists.
Retain Data, AbstractData and StringData from part (c). The following are the additional software classes. Formatting denotes the supplied formatting facility with its two static format overloads; its implementation is expressly not required. These calls preserve the distinction between a minimum width and a maximum width: no stored value is truncated.
abstract class NumericData extends AbstractData {
    private int minDigits = 0;

    protected NumericData(boolean leftj) { super(leftj); }

    public final void setDigits(int n) { minDigits = Math.max(0, n); }
    protected final int digits() { return minDigits; }
}

final class IntegerData extends NumericData {
    private final int value;

    public IntegerData(int n, boolean leftj) {
        super(leftj);
        value = n;
    }

    public String toString() {
        return Formatting.format(value, digits());
    }
}

final class RealData extends NumericData {
    private final double value;
    private int minPlaces = 0;

    public RealData(double d, boolean leftj) {
        super(leftj);
        value = d;
    }

    public void setPlaces(int p) { minPlaces = Math.max(0, p); }

    public String toString() {
        return Formatting.format(value, digits(), minPlaces);
    }
}
Zero is the default minimum, and a nonpositive setting removes that minimum. Formatting a negative value, or a value already longer than the minimum, is delegated to the stated formatter contract. The inherited length() calls the current toString(), so a change to either formatting setting immediately changes the measured column width. For example, after setDigits(3), an IntegerData containing 42 renders 042 and has length 3; after setPlaces(2), a RealData containing 2.7 renders 2.70 and has length at least 4.
Unlike StringData, these numeric software objects are mutable because their displayed state can change. Their numeric values and alignment remain fixed. The useful invariant is
The UML class diagram separates text shared by every displayable item from numeric formatting shared only by numeric items. A dashed hollow-triangle arrow denotes realization of a Java interface; solid hollow-triangle arrows denote class inheritance. Both kinds of arrow point towards the more general type.
Figure 1.
Data interface realization and inheritance for string, integer and real display items
. Details.
AbstractData owns alignment and computes length from the current rendered text. NumericData adds the minimum digit width. IntegerData and RealData each own their numeric value, while RealData alone owns the minimum number of decimal places. The numeric formatting object methods do not belong on Data: ordinary text has no meaningful setPlaces operation. The design choice is
The problem is undecidable. Reduce the halting problem to it. Given a Turing machine and input word , construct a Turing machine over with the following behavior on input :
  • If , reject.
  • If , simulate on the fixed word . If that simulation ever halts, whether accepting or rejecting, accept ; otherwise continue the simulation forever.
This is an effective construction: are fixed data stored in the description of . Its recognized formal language is
Therefore accepts exactly one input word if and only if halts on . A supposed decision procedure for the singleton-language problem for Turing machines, applied to the constructed , would decide the halting problem. The standard undecidability of the halting problem excludes that possibility.
The problem is decidable. We need exactly one accepted word, even if that word has several accepting runs in the nondeterministic finite automaton.
First convert the input nondeterministic finite automaton to an equivalent deterministic finite automaton using the subset construction, taking epsilon closure where necessary. In the finite transition directed graph of , test whether an accepting automaton state is reachable from the initial automaton state. This is the standard finite automaton emptiness test. If none is reachable, the recognized formal language is empty, so answer no.
Otherwise retain a graph path to an accepting automaton state and read its labels to obtain one accepted word . If the initial automaton state is accepting, may be the empty word. Build a complete deterministic finite automaton for the singleton formal language : it tracks the matching prefix of , accepts only after exactly its full length, and enters a rejecting sink on a mismatch or any extra input symbol.
Complement that complete deterministic finite automaton by exchanging accepting and rejecting automaton states. Form its product with , accepting exactly when the coordinate accepts and the other coordinate accepts. This product recognizes
Apply the finite automaton emptiness test again. Answer yes if and only if this difference is empty. The first test guarantees that belongs to ; the second guarantees there is no different accepted word. All constructions have finitely many automaton states and all reachability tests terminate. This gives a singleton-language test for finite automata.
The formal language is not a context-free language. Suppose otherwise, and let be a pumping length from the pumping lemma for context-free languages. Choose
This word belongs to the formal language, since its middle exponent is the product of the two outer exponents. The pumping lemma for context-free languages would give
with in the formal language for every integer .
Let be the respective numbers of symbols in the two pumped pieces together. The window cannot contain both an and a : it would have to contain the entire middle block of length , plus at least those two outer symbols, exceeding . Hence
Pump once extra, taking . The resulting symbol counts are , , and . A necessary condition for membership, regardless of whether the block order survives, is
where was used.
If , then , contradicting that equality. If , then
again contradicting it. Thus every permissible decomposition fails at . This contradicts the pumping lemma for context-free languages and proves the claim. The obstruction is the multiplicative block-count language: a bounded local change cannot preserve the product constraint.
The formal language is a context-free language. A context-free grammar with start nonterminal symbol is
The production rule for nests one on the left and one on the right on each recursive use, so generates exactly for . Similarly, generates exactly for . The start production rule concatenates these words, yielding
Conversely, every choice of nonnegative integers is achieved by using the recursive production rules exactly times before their epsilon productions. Hence this context-free grammar generates precisely the required formal language, including all cases where either count is zero.
The formal language is not a regular language. Let denote it and consider the infinitely many prefixes
For any , append the word . Then , whereas : the latter word has occurrences of and occurrences of , and every word of has equal numbers of those two symbols.
Thus and are not Myhill-Nerode equivalent. There are infinitely many Myhill-Nerode equivalence classes, so the Myhill-Nerode theorem rules out a finite-state automaton recognizing . Equivalently, if two such prefixes left a deterministic finite automaton in the same automaton state, appending could not distinguish their acceptance, giving the same contradiction.
The formal language is a regular language. A regular expression for it is
The first Kleene star independently chooses copies of the word , and the second independently chooses copies of . Their concatenation produces exactly the required words. Either count may be zero, including both counts zero, which gives the empty word. By Kleene theorem, the regular expression establishes regularity.
Every generated word satisfies
where count occurrences of the indicated terminal symbols. To see this, follow the unique chain of occurrences in a parse tree. Each use of introduces one from , at least one from its rightmost , and possibly one further from . Each use of adds one and no . The terminating contributes neither. Hence no generated word has more symbols than symbols.
Also, for every , the word is generated: apply exactly times, choose each time, then use and all remaining .
Suppose were a regular language, and let be a pumping length from the pumping lemma for regular languages. Apply it to . Every allowed decomposition with and has for some . Pumping twice gives
which violates the proved counting inequality and hence is not generated. This contradicts the pumping lemma for regular languages. Therefore is not a regular language. Ambiguity was not used: the obstruction is the unbounded constraint on symbol counts.
Use the standard conversion of a context-free grammar to a pushdown automaton, implementing a leftmost derivation on a stack. Take control states , input alphabet , stack alphabet , initial control state , initial stack symbol , and sole final control state . The symbol is a fresh stack bottom marker. As in part (a), the top of the stack is written on the left.
Initialize with
In control state , replace a top nonterminal symbol by one of its production rule right-hand sides:
The replacements are written in the order in which they are to be processed. For example, replacing by leaves on top; an implementation using individual push operations pushes , then , then .
Match and pop top terminal symbols by
Finally include
All unlisted transitions have no choices; has no outgoing transitions. This is acceptance by final state, leaving the bottom marker on the stack. Taking the last transition too early cannot cause false acceptance, because an unread input suffix remains and cannot consume it.
For correctness, after initialization the stack contains the unprocessed part of a sentential form. Expanding a top nonterminal symbol simulates one step of a leftmost derivation, and popping a matching terminal symbol transfers it to the already-read input prefix. Thus if the input prefix consumed so far is and the stack above is , then . Acceptance gives for the entire input .
Conversely, any leftmost derivation of specifies choices of these transitions: expand the next nonterminal symbol, and read each resulting leading terminal symbol when it reaches the top. After all symbols of are consumed, only remains, enabling the move to . The nondeterministic pushdown automaton therefore recognizes exactly . The empty word is accepted by choosing after initialization.
The word has these two leftmost derivations:
In the first grammar derivation, supplies an extra ; the remaining goes directly to the empty word. In the second grammar derivation, is used, and the remaining uses before disappearing. Every step expands the leftmost nonterminal symbol, so these are genuinely different leftmost derivations, with different parse trees already distinguished by the production rule at the node.
Therefore is an ambiguous grammar, witnessed by .
A context-free grammar is an ambiguous grammar if some word in its generated formal language has two distinct parse trees. Equivalently, that word has two distinct leftmost derivations from the start nonterminal symbol. A leftmost derivation always expands the leftmost remaining nonterminal symbol.
Two arbitrary grammar derivations of the same word do not by themselves prove ambiguity: expanding independent nonterminal symbols in a different order can describe the same parse tree. Requiring distinct parse trees, or distinct leftmost derivations, avoids that issue.
Use state elimination for finite automata, with regular expression labels on a generalized finite automaton. Add a fresh initial automaton state with , and a fresh final automaton state with . Only is now accepting. Missing labels represent the empty language, and parallel alternatives are combined by union.
When eliminating an internal automaton state , update every surviving label by
The added regular expression describes entering , traversing its loop zero or more times by Kleene star, and leaving it. This accounts for exactly the graph paths newly bypassing .
First eliminate . Its only incoming and outgoing labels are both , and it has no loop. The graph path through it contributes , so the label from to becomes
The other relevant labels are still , , and .
Next eliminate . It has no loop, so the new loop at and the new label to are
Finally eliminate . The label from to is
Thus an equivalent regular expression is
For an independent interpretation, every completed return to consumes either or : the latter traverses before returning. The last visit to consumes either nothing or . Consequently every run of ones has length exactly two, and successive such runs require at least one zero between them. In particular, consecutive copies of without a separating zero are not accepted.
For , there is an accepting graph path
Its nonempty labels spell , and its last automaton state is accepting. Therefore is accepted. The last epsilon transition matters: finishing the consumed input at does not prevent a subsequent move to .
For , track all possible automaton states, including their epsilon closure, after each input prefix:
Input prefixPossible automaton states after epsilon closure
The final set contains no accepting automaton state, and has no outgoing epsilon transition. Therefore is rejected.
Lucy's happiness is a single antecedent, while the conclusion applies to everyone:
Since does not occur in the antecedent, this is equivalent to . The universal quantifier does not assert that everyone is happy; it is the merriness conclusion that is universal.
The same person must both love and be loved by :
Equivalently, use . There is no restriction that and be distinct; this matters when the later ground resolution proof considers Lucy loving herself.

Pinned article: Introduction to the OurBigBook Project

Welcome to the OurBigBook Project! Our goal is to create the perfect publishing platform for STEM subjects, and get university-level students to write the best free STEM tutorials ever.
Everyone is welcome to create an account and play with the site: ourbigbook.com/go/register. We belive that students themselves can write amazing tutorials, but teachers are welcome too. You can write about anything you want, it doesn't have to be STEM or even educational. Silly test content is very welcome and you won't be penalized in any way. Just keep it legal!
We have two killer features:
  1. topics: topics group articles by different users with the same title, e.g. here is the topic for the "Fundamental Theorem of Calculus" ourbigbook.com/go/topic/fundamental-theorem-of-calculus
    Articles of different users are sorted by upvote within each article page. This feature is a bit like:
    • a Wikipedia where each user can have their own version of each article
    • a Q&A website like Stack Overflow, where multiple people can give their views on a given topic, and the best ones are sorted by upvote. Except you don't need to wait for someone to ask first, and any topic goes, no matter how narrow or broad
    This feature makes it possible for readers to find better explanations of any topic created by other writers. And it allows writers to create an explanation in a place that readers might actually find it.
    Figure 1.
    Screenshot of the "Derivative" topic page
    . View it live at: ourbigbook.com/go/topic/derivative
  2. local editing: you can store all your personal knowledge base content locally in a plaintext markup format that can be edited locally and published either:
    This way you can be sure that even if OurBigBook.com were to go down one day (which we have no plans to do as it is quite cheap to host!), your content will still be perfectly readable as a static site.
    Figure 5. . You can also edit articles on the Web editor without installing anything locally.
    Video 3.
    Edit locally and publish demo
    . Source. This shows editing OurBigBook Markup and publishing it using the Visual Studio Code extension.
  3. https://raw.githubusercontent.com/ourbigbook/ourbigbook-media/master/feature/x/hilbert-space-arrow.png
  4. Infinitely deep tables of contents:
    Figure 6.
    Dynamic article tree with infinitely deep table of contents
    .
    Descendant pages can also show up as toplevel e.g.: ourbigbook.com/cirosantilli/chordate-subclade
All our software is open source and hosted at: github.com/ourbigbook/ourbigbook
Further documentation can be found at: docs.ourbigbook.com
Feel free to reach our to us for any help or suggestions: docs.ourbigbook.com/#contact