Turing Machine
Turing machines extend finite state machines with infinite memory, read-write capability, and bidirectional movement, enabling them to model all computable problems.
Notes
Learning notes, reading summaries, and quick references
Context-Free Language
Context-free grammars define context-free languages using production rules and parse trees, with pushdown automata as their recognizing machines, forming a superset of regular languages.
Regular Languages
Regular languages are recognized by finite state machines, described by regular expressions, and generated by regular grammars, with union, concatenation, and Kleene star operations.
Finite State Machine
A finite state machine, defined by states, alphabet, transitions, start and final states, recognizes exactly one regular language.
Nondeterministic Finite State Machines NFSM
Nondeterministic finite state machines allow multiple possible next states for an input, including epsilon transitions, but are equivalent to deterministic FSMs via subset construction.