Finite Automata Overview

Study Notes

A finite automaton is a mathematical model of computation that consists of a finite set of states, a finite set of input symbols, and a transition function that maps states and input symbols to new states.
Deterministic Finite Automata (DFA) have a single, deterministic transition for each state and input symbol.
Non-deterministic Finite Automata (NFA) allow for multiple transitions for a given state and input symbol.
Transition Systems are the set of relationships that define the behavior of the finite automaton. They include states, input symbols, and transitions.
Acceptance of a string by a finite automaton is determined by whether the automaton reaches an accepting state after reading the entire input string.
Mealy and Moore machines are two types of finite state machines that differ in how they output. Mealy outputs depend on the current state and input, while Moore outputs depend solely on the current state.
Minimization of finite automata is the process of reducing the number of states in a finite automaton while preserving its language recognition capabilities.

Regular expressions are a concise way to represent regular languages.
Regular expressions use operators such as union, concatenation, and Kleene closure to combine simpler expressions.
Regular expressions and finite automata are equivalent in terms of their expressive power. They can represent the same set of languages.
The pumping lemma for regular sets is a tool used to prove that a language is not regular. It states that any sufficiently long string in a regular language can be "pumped" by repeating a substring multiple times.

A formal language is a set of strings formed from a finite alphabet. They are defined using formal grammars.
Chomsky hierarchy classifies formal languages into four types based on the complexity of their grammars:
- Type 0: unrestricted grammars
- Type 1: context-sensitive grammars
- Type 2: context-free grammars
- Type 3: regular grammars

Regular grammars generate regular languages and are closely related to regular expressions.
Converting regular expressions to regular grammars and vice versa is possible.
Regular grammars can be left linear or right linear; this relates to what is added to the right or left of the nonterminal during rewriting.

Context-free grammars (CFG) are a type of formal grammar that allows for the generation of context-free languages.
CFGs use productions to rewrite non-terminal symbols into combinations of terminals and non-terminals.
Ambiguity in CFGs occurs when a string can be derived in multiple ways.
Leftmost and rightmost derivations are ways to systematically derive strings from a CFG.
The pumping lemma for CFLs is used to prove that a language is not context-free.
Normal forms such as Chomsky Normal Form and Greibach Normal Form simplify CFGs without changing their language.
Reduced grammars remove redundant productions and inaccessible non-terminals.

Pushdown automata (PDA) extend Finite Automata by adding a stack. This allows them to recognize context-free languages.
Acceptance in a PDA is based on the stack state after the input is read.
Deterministic PDAs (DPDA) have a single, deterministic transition for each state and input symbol. Non-deterministic PDAs (NDPDA) allow for multiple transitions.
Parsing involves transforming a string in a formal language into its corresponding parse tree.
LL(k) and LR(k) grammars serve as building blocks for efficient parsing algorithms.

Turing machines are theoretical models of computation that can simulate any algorithm.
A Turing Machine consists of a finite state control, a tape, and a read/write head.
The Halting Problem for Turing Machines is undecidable, meaning there exists no algorithm to determine if any given program will stop or run indefinitely.
The Post Correspondence Problem is another undecidable problem related to Turing machines.
Computational complexity focuses on the resources (time and space) required to solve problems with a Turing machine.
Linear-Bounded Automata (LBA) are a type of Turing machine where the tape length is bounded, making them potentially less powerful than general Turing machines.
Cellular automata are a computational model where the state of each cell is updated based on a deterministic rule and the states of its neighbors.