Prajun Trital·Oct 25Review 1: From Sets to NFAsThis post pulls together the first ten posts of the series, from sets and proofs up to nondeterministic finite automata. For each topic…
Prajun Trital·Oct 24Nondeterministic Finite Automata (NFA)In the last post, we ran into a wall: a DFA has no simple way to recognize the concatenation of two languages, because it can’t know where…
Prajun Trital·Oct 24Regular Operations and the Product ConstructionIn the last post, we designed each DFA by hand, one language at a time, using intuition. That works for small languages, but it doesn’t…
Prajun Trital·Sep 29Deterministic Finite Automata (DFA)In the previous post, we saw that the simplest machines have finite memory: they carry forward nothing but their current state. In this…
Prajun Trital·Sep 29Transition Functions, Memory, and Decision ProblemsIn the last two posts, we built the ingredients of a machine: states, an alphabet, strings, and languages. In this post, we design the most…
Prajun Trital·Sep 29Alphabets, Strings, and LanguagesIn the previous post, we listed the ingredients of a computation: states, inputs and outputs, transitions, a start state, and stop states…
Prajun Trital·Sep 29Abstracting a Computer: States and Computation GraphsWith the math foundations in place, we can turn to the central question of this course: what is a computer, really? In this post, we’ll…
Prajun Trital·Sep 27Proof by Contradiction and CountabilityIn the previous post, we built equivalence classes and claimed that the classes of fractions form a partition. In this post, we’ll prove…A response icon1A response icon1
Prajun Trital·Sep 27Modular Arithmetic, Equivalence Classes, and PartitionsIn the previous post, we met equivalence relations: relations that are reflexive, symmetric, and transitive. In this post, we’ll see what…
Prajun Trital·Sep 26Relations, Functions, and Their PropertiesIn the previous post, we built the Cartesian product, the set of all ordered pairs from two sets. In this post, we’ll use it to define…
