Syntactic Analysis
Syntactic analysis transforms token sequences into parse trees using grammar rules, employing top-down or bottom-up strategies evaluated on power, backtracking, lookahead, efficiency, and size.
Notes
Learning notes, reading summaries, and quick references
Lexical Analysis
Lexical analysis converts source code into tokens by removing whitespace and comments, using finite-state machines for efficient recognition and classification.
Turing Machine
Turing machines extend finite state machines with infinite memory, read-write capability, and bidirectional movement, enabling them to model all computable problems.
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.