1.2Logic & automata

The previous section covered how numbers themselves are represented. This section moves into the world of logic: how truth values are combined to reach a decision. From the logical operations underlying an if statement to the mechanisms compilers use to check syntax (BNF, automata), this is foundational to pseudocode and programming in general.

1.2.1Logical operations and De Morgan's laws

• Logical operations act on the two values true and false. The three basics are AND (conjunction), OR (disjunction), and NOT (negation), corresponding to and/or/not in pseudocode conditions.
• De Morgan's laws relate negation to AND and OR: NOT (A AND B) = (NOT A) OR (NOT B) and NOT (A OR B) = (NOT A) AND (NOT B). They are used to break down a complex negated condition into a more readable form.
• Practical use: the condition not (in-stock and payment-succeeded) can be rewritten via De Morgan's laws as out-of-stock or payment-failed, making the intent of the branch far easier to read.

1.2.2Logic circuits

• A logic circuit physically implements logical operations as electronic circuitry. The basic gates are the AND gate, OR gate, and NOT gate; combining them builds more complex circuits such as an adder.
• XOR (exclusive OR) is true only when the two inputs differ. It can be built from AND/OR/NOT gates, and is frequently used, for example, in the sum-without-carry part of an adder.

1.2.3BNF and regular expressions

• BNF (Backus-Naur Form) is a notation for rigorously defining the syntax (grammar) of a programming language or protocol. Rules are written as <syntax-element> ::= definition and stacked recursively; it underlies a compiler's syntax analysis.
• A regular expression is a notation for describing a pattern in a string, using metacharacters such as * (zero or more repetitions), + (one or more), and | (alternation). It is used for input validation (e.g., checking an email-address format) and string search.
• BNF and automata share the goal of verifying that syntax is well-formed, but BNF is suited to describing hierarchical syntactic structure, while a finite automaton is suited to accepting simpler patterns (equivalent to a regular expression) via state transitions.

1.2.4Finite automata

• A finite automaton (finite state machine) is a computational model made of a finite set of states and state-transition rules driven by input. Starting from an initial state, it reads an input symbol string one symbol at a time, transitioning between states, and "accepts" the input if it ends in an accepting state.
• Familiar examples: a vending machine (state transitions driven by the amount inserted), traffic-light control, and the internal implementation of a regular-expression engine. The name "finite" automaton comes from having a finite number of states.

Suppose an EC site's order-confirmation logic implements the pseudocode condition if not (in-stock and payment-succeeded) then show error, and a reviewer flags that "the combination of negation and and is hard to read." Applying De Morgan's laws, NOT (in-stock AND payment-succeeded) is equivalent to (NOT in-stock) OR (NOT payment-succeeded), so the condition can be rewritten as if (out-of-stock or payment-failed) then show error. Both versions return exactly the same logical result, but the second makes the intent—"show an error if either the item is out of stock or payment failed"—clear at a glance. Next, consider designing how this system tracks order status (unconfirmed -> confirmed -> shipped -> complete, plus cancellation). Enumerating the states and the transition rules triggered by confirm/ship/cancel events lets you model this directly as a finite automaton, which mechanically catches invalid transitions such as "a ship event on an already-cancelled order." Finally, to validate that an order-number field follows the format "two letters followed by six digits," a regular expression such as ^[A-Z]{2}[0-9]{6}$ expresses that pattern—and that regular expression itself is typically implemented internally as a finite automaton. Logical operations, De Morgan's laws, automata, and regular expressions are all connected by this one consistent purpose: correctly judging inputs and conditions.

1.2.5Section summary

• De Morgan's laws: NOT(A AND B)=(NOT A)OR(NOT B), NOT(A OR B)=(NOT A)AND(NOT B) (negation swaps AND and OR)
• BNF = recursive definition of syntax, regular expressions = describing string patterns—both are used to judge the validity of syntax or input
• Finite automata = a finite set of states plus transition rules that model behavior; used for state management and to implement regular expressions internally