🧩Discrete Mathematics Unit 11 – Modeling Computation

Key Concepts and Terminology

• Alphabet ($\Sigma$) finite, non-empty set of symbols used to form strings
• String finite sequence of symbols from an alphabet
• Language ($L$) set of strings over a given alphabet
• Deterministic Finite Automaton (DFA) finite state machine that accepts or rejects strings, transitioning between unique states
  • Formally defined as a 5-tuple ($Q$, $\Sigma$, $\delta$, $q_0$, $F$)
• Non-deterministic Finite Automaton (NFA) finite state machine that can have multiple transitions for the same input, and can transition without consuming input
• Regular expression concise way to describe regular languages using operators (union, concatenation, Kleene star)
• Context-free grammar (CFG) set of production rules that generate strings in a context-free language
  • Consists of terminals, non-terminals, production rules, and a start symbol
• Turing machine abstract computational model that manipulates symbols on an infinite tape according to a set of rules
• Decidability property of a problem being solvable by an algorithm in a finite number of steps
• Time complexity measure of the amount of time an algorithm takes to run as a function of input size

Finite State Automata

• Mathematical model for describing and recognizing regular languages
• Consists of states, transitions between states, and a set of accepting states
• Input is processed one symbol at a time, causing transitions between states
• Accepts a string if the automaton reaches an accepting state after processing the entire input
• DFAs have exactly one transition for each input symbol in each state
  • Deterministic behavior allows for efficient string recognition
• NFAs can have multiple or no transitions for each input symbol in each state
  • May also have $\varepsilon$-transitions that allow state changes without consuming input
• Every NFA can be converted to an equivalent DFA using the subset construction algorithm
• Used in various applications (lexical analysis, pattern matching, network protocols)

Regular Languages and Expressions

• Regular languages are the class of languages recognizable by finite automata (DFAs and NFAs)
• Can be described using regular expressions, which are concise representations of regular languages
• Regular expressions consist of symbols from the alphabet, along with operators:
  • Union ($|$) represents the choice between two subexpressions
  • Concatenation (often denoted by juxtaposition) represents the sequential combination of subexpressions
  • Kleene star ($*$) represents zero or more repetitions of a subexpression
• Regular expressions can be converted to equivalent NFAs or DFAs
• Closure properties of regular languages include closure under union, concatenation, and Kleene star
• Pumping Lemma for regular languages provides a necessary condition for a language to be regular
  • Used to prove that certain languages are not regular (e.g., $\{a^nb^n | n \geq 0\}$)

Context-Free Grammars

• Generative models for describing context-free languages, which are a superset of regular languages
• Consist of a set of production rules that replace non-terminal symbols with strings of terminals and non-terminals
• Production rules have the form $A \to \alpha$, where $A$ is a non-terminal and $\alpha$ is a string of terminals and non-terminals
• Start symbol is a designated non-terminal from which all derivations begin
• Derivation is a sequence of rule applications that generates a string in the language
• Chomsky Normal Form (CNF) is a restricted form of CFGs where production rules are limited to two non-terminals or one terminal
  • Every CFG can be converted to an equivalent grammar in CNF
• Parsing is the process of determining if a string belongs to the language generated by a CFG
  • CYK algorithm is a parsing algorithm for grammars in CNF
• Used to describe programming language syntax, natural language structures, and in compiler design

Turing Machines

• Abstract computational model that extends finite automata with an infinite tape and read/write capabilities
• Consists of a tape divided into cells, a read/write head, a state register, and a transition function
• Tape holds an infinite sequence of symbols, with each cell initially blank (denoted by a special blank symbol)
• Read/write head can move left or right on the tape, reading and writing symbols
• State register holds the current state of the machine, which determines the next action based on the transition function
• Transition function specifies the next state, symbol to write, and head movement based on the current state and symbol read
• Computation begins in the initial state with the input string on the tape, and continues until a halting state is reached
• Recognizes a language if it enters an accepting state for strings in the language, and a rejecting state otherwise
• Universal Turing Machine is a Turing machine that can simulate any other Turing machine given its description and input
• Serves as a theoretical foundation for computability and complexity theory

Computability and Decidability

• Computability theory studies the limits of computation and the problems that can be solved by algorithms
• Decidable problems are those for which an algorithm can provide a correct yes/no answer for any input in a finite number of steps
  • Examples include determining if a string belongs to a regular language or if a CFG generates a given string
• Undecidable problems are those for which no algorithm can provide a correct answer for all inputs in a finite number of steps
  • Halting problem (determining if a Turing machine will halt on a given input) is a famous example of an undecidable problem
• Recognizable problems are those for which a Turing machine can enter an accepting state for inputs with a "yes" answer, but may not halt for inputs with a "no" answer
• Rice's Theorem states that any non-trivial property of the language recognized by a Turing machine is undecidable
• Recursively enumerable languages are those for which a Turing machine can enumerate all strings in the language
  • All decidable languages are recursively enumerable, but not vice versa

Complexity Theory Basics

• Studies the resources (time, space) required to solve computational problems
• Time complexity measures the number of steps an algorithm takes as a function of input size
  • Big O notation describes an upper bound on the growth rate of a function
• Space complexity measures the amount of memory an algorithm uses as a function of input size
• Polynomial-time algorithms are those with time complexity bounded by a polynomial function of the input size
  • Class P represents problems solvable in polynomial time by deterministic Turing machines
• Nondeterministic polynomial-time (NP) algorithms are those that can be verified in polynomial time by deterministic Turing machines
  • Class NP represents problems solvable in polynomial time by nondeterministic Turing machines
• NP-complete problems are the hardest problems in NP, to which all other NP problems can be reduced in polynomial time
  • Examples include Boolean Satisfiability (SAT), Traveling Salesman Problem (TSP), and Graph Coloring
• NP-hard problems are at least as hard as NP-complete problems, but may not be in NP themselves
• P versus NP problem is the open question of whether P = NP, or if there are problems in NP that are not in P

Real-World Applications

• Regular expressions are used in text processing, pattern matching, and lexical analysis in compilers
• Finite automata are used in string searching algorithms (Knuth-Morris-Pratt, Boyer-Moore)
  • Also used in network protocol design, digital circuit design, and natural language processing
• Context-free grammars are used to define programming language syntax and in parsing algorithms for compilers
  • Also used in natural language processing and RNA secondary structure prediction
• Turing machines serve as a theoretical foundation for computability and complexity theory
  • Used to study the limits of computation and classify problems based on their solvability
• Decidability and undecidability results help identify problems that cannot be solved by algorithms
  • Used in program verification, automated theorem proving, and analysis of cryptographic protocols
• Complexity theory is used to analyze the efficiency of algorithms and classify problems based on their resource requirements
  • Helps guide the development of efficient algorithms and approximation techniques for hard problems
• NP-completeness is used to identify computationally challenging problems in various domains
  • Informs the development of heuristics, approximation algorithms, and problem-specific solutions
• Applications of complexity theory include optimization, scheduling, cryptography, and machine learning