Automata and Languages

One fact decides it: the state the machine is left in after the final symbol. If that state is in the accepting set, the string is accepted. Passing through an accepting state earlier in the run means nothing.

Run both machines at once. The product automaton's states are pairs (p, q), one component per machine, and each input symbol advances both components. Mark a pair accepting when both components accept, and you have the intersection.

Determinism means exactly one successor for every state-and-symbol pair, so the transition rule must be total and no run can ever get stuck. Symbols a rule forbids are usually routed to a non-accepting trap state that absorbs the rest of the input.

Two states are distinguishable when some remaining input is accepted from one and rejected from the other; that string is the witness. States with no such witness behave identically on every future input and can be merged without changing the accepted language.

Acceptance is existential: the machine accepts a string when at least one run over it ends in an accepting state. Runs that die on a missing transition, or finish in a non-accepting state, simply contribute nothing.

A greedy quantifier takes as many repetitions as it can and gives characters back only when the rest of the pattern fails; a lazy one takes as few as possible and grows one at a time.

The Kleene star means zero or more repetitions of the subexpression it follows, joined end to end. Zero is the trap: a starred part can match the empty string, so on its own it never forces that text to be present.

A live state set records where the pattern is, not what the text matched. A backreference demands that an arbitrarily long captured substring occur again, and no fixed set of machine states can carry that text forward.

A backtracking engine explores one alternative at a time and rewinds the input when a branch fails. A state-set engine advances every live alternative together, consuming each input character exactly once.

Searching asks whether a match exists anywhere in the subject, not whether the whole subject matches. Without a start and end anchor, a pattern for four digits happily matches the four digits buried inside a longer string.

Terminals are the literal symbols that appear in the generated text; nonterminals are named placeholders that some rule rewrites. A derivation starts at one designated start symbol and rewrites nonterminals until only terminals remain.

Ambiguity means the grammar admits two distinct parse trees for one string, so the tree — and therefore the meaning the string denotes — is not fixed by the grammar alone. Two conforming parsers may legitimately disagree.

Both rewrite the same nonterminal occurrences by the same rules, but in a different order: a leftmost derivation always rewrites the leftmost nonterminal of the current line, a rightmost derivation always the rightmost one. The intermediate lines differ; the rule applications do not.

The stack is memory that grows with the input, so the machine can match nesting of any depth: push a marker on every opener, pop and compare on every closer, and accept a run whose store ends exhausted.

Split the alternatives: replace A -> A alpha | beta with A -> beta A2 and A2 -> alpha A2 | empty. The recursive part becomes a repeating tail, so the parser consumes the leading beta before re-entering and the recursion terminates.

Each Chomsky tier restricts rule shape. Type 3: one terminal plus at most one non-terminal on the right, every rule leaning the same way. Type 2: a single non-terminal on the left. Type 1: no rule shortens. Type 0: unrestricted.

Turing complete means the model can simulate an arbitrary Turing machine, so it computes exactly the functions a Turing machine computes. You demonstrate it by building an interpreter for an already-complete model, such as a register machine, inside the candidate.

A Turing machine step reads the one symbol under the head and, using the table entry for that state-symbol pair, writes a symbol into that same cell, moves the head one cell left or right, and enters the next state.

Type 2, context-free. Arbitrarily deep nesting means the number of unclosed blocks is unbounded, and a finite-state validator can distinguish only finitely many histories. The validator needs memory that grows with depth, so it is a parser, not a pattern.

One rung, one kind of memory. A finite-state machine holds only its current state. A pushdown machine adds an unbounded store where only the newest symbol is readable. A linear-bounded machine adds re-readable space no larger than the input. A tape machine removes the size limit.

Panic mode discards tokens until it reaches one from a synchronising set — a statement delimiter, block closer or declaration keyword — then unwinds its suspended rules until one accepts that token, and parses on.

Shift pushes the next input token onto the parse stack; reduce recognises a handle, a complete right-hand side sitting on top, pops those symbols and pushes the rule's left-hand nonterminal. The generated table decides which, per state and lookahead.

Ordered choice commits to the first alternative that succeeds at a position, so each rule yields at most one result there. The grammar defines one recognizer rather than a set of permitted derivations, so a second parse tree cannot exist.

The power handed to the right-operand recursion decides it: recursing with the operator's power plus one makes it left-associative, because an equally binding operator is then refused; recursing with the same power makes it right-associative.

A binding power is a number per operator saying how tightly it grips its neighbours. One loop parses an operand, then keeps absorbing operators whose power clears the caller's minimum, recursing once per right operand.

A token is one lexical unit: a class such as identifier, number, keyword, operator or punctuator, together with its text and the source span it came from. The scanner throws away whitespace and comments but keeps the spans.

Compilation costs time, CPU and memory, and most methods run only a handful of times. Counting invocations and loop iterations finds the small hot fraction where optimisation will be repaid, and the interpreted phase supplies the profile the compiler then optimises against.

An abstract syntax tree keeps operators, operands and structure, and drops what only guided the parser: grouping parentheses, separators and terminators, layout, and single-child chain nodes from precedence rules. The tree's shape already encodes the grouping those tokens expressed.

Three-address code gives every intermediate value a name and every operation its own instruction in a fixed order. Evaluation order and the producer of each value become explicit data rather than facts implied by a tree walk.

It takes the longest prefix starting at that position that any rule accepts, not the first rule that matches. If two rules accept the same longest prefix, the rule declared earlier wins.