16 terms in 3.4
Computation theory
Abstract computational models with finite states, transitions triggered by input symbols, and optional output. Finite st
Theory of computation
Computation theory
Formal notation describing patterns of character sequences using metacharacters and operators. Regular expressions enabl
Theory of computation
Computation theory
Backus-Naur Form is a formal notation for specifying grammar rules and syntax of languages. BNF defines context-free gra
Theory of computation
Computation theory
Graphical representations of grammar rules showing valid language syntax through flowchart-like diagrams. Syntax diagram
Theory of computation
Computation theory
A state machine with finite states where each input leads to exactly one transition. DFAs recognize regular languages an
Theory of computation
Computation theory
A state machine where input may cause transitions to multiple states or enable epsilon transitions. NFAs are more expres
Theory of computation
Computation theory
State machines where output depends on current state and input. Mealy machines typically require fewer states than Moore
Theory of computation
Computation theory
State machines where output depends only on current state. Moore machines often require more states than Mealy machines
Theory of computation
Computation theory
Automata with finite states plus a stack enabling recognition of context-free languages. Pushdown automata are more powe
Theory of computation
Computation theory
Mathematical notation for describing collections of elements with operations and properties. Set notation enables formal
Theory of computation
Computation theory
Properties showing that regular languages are closed under union, concatenation, and Kleene star operations. Closure pro
Theory of computation
Computation theory
Computational problems with yes/no answers. Decision problems form basis of computability theory. Solvability classifica
Theory of computation
Computation theory
Functions computable by algorithms versus functions without computing procedures. Computability connects to Turing machi
Theory of computation
Subtopic b
Abstract computational models consisting of infinite tape, read-write head, finite control, and state transitions. Turin
Theory of computation
Subtopic b
The study of what problems can be solved by computational processes and which are fundamentally unsolvable. Computable f
Theory of computation
Subtopic b
The undecidable problem of determining whether an arbitrary program terminates or loops infinitely. Proving the halting
Theory of computation