"A finite-state machine (FSM) or finite-state automaton (FSA, plural: automata), finite automaton, or simply a state machine, is a mathematical model of computation."
Finite automata are abstract machines that can recognize regular languages. DFAs are a type of finite automata that have a single accept state, while NFAs can have multiple accept states.
Regular languages: Regular languages are a class of languages that can be expressed through regular expressions or finite automata.
Deterministic finite automata (DFA): DFAs are a type of finite automaton that accepts or rejects a given input string based on a series of states and transitions.
Nondeterministic finite automata (NFA): NFAs differ from DFAs in that they can have multiple possible states for a given input, creating a branching path.
Regular expressions: Regular expressions are a language used to describe patterns in strings, and can be used to define regular languages.
Equivalence between DFAs and NFAs: Proving the equivalence between DFAs and NFAs is important in determining the expressive power of finite automata.
Closure properties of regular languages: Understanding the closure properties of regular languages is useful in determining if certain operations on regular languages will result in another regular language.
Pumping lemma: The pumping lemma is a tool used to prove that certain languages are not regular.
Myhill-Nerode theorem: The Myhill-Nerode theorem is a tool for determining the minimum number of states needed in a DFA to recognize a regular language.
Regular grammars: Regular grammars are a type of grammar that generate regular languages.
Kleene's theorem: Kleene's theorem states that regular languages can be defined by regular expressions, finite automata, or regular grammars.
Minimization of DFAs: Minimizing a DFA involves reducing the number of states while still recognizing the same language, resulting in a more efficient automaton.
State minimization algorithms: There are multiple algorithms that can be used to minimize a DFA, including the table-filling algorithm and the Hopcroft's algorithm.
Regular language intersection and complementation: Understanding regular language intersection and complementation is useful in determining if operations on regular languages will result in another regular language.
Decidability of regular languages: Proving the decidability of regular languages is important in determining if a given language is regular or not.
Finite automata and their application to real-world problems: Finite automata have many practical applications, such as in designing electronic circuits or in natural language processing.
Deterministic Finite Automata (DFA): It is a type of finite automata in which for each input symbol, there is one unique transition leading to a new state.
Non-Deterministic Finite Automata (NFA): It is a type of finite automata in which for each input symbol, there can be multiple transitions leading to new states.
ε-NFA: It is a type of NFA which allows epsilon transitions. These transitions occur without reading any input, and they change the state of the automata without any input symbol.
Mealy Machine: It is a type of finite automata that generates an output or action based on the current state and the input symbol.
Moore Machine: This type of finite automata generates an output based on the current state only.
Pushdown Automata (PDA): It is a type of finite automata which is equipped with a stack, and it uses this stack to store and retrieve data.
Turing Machine: It is a type of finite automata in which an infinite tape is used to store data, it has a head which reads and writes data on the tape, and there is a set of rules to change the state of the machine.
Linear Bounded Automata (LBA): It is a type of Turing machine that can only use a linear amount of space on the tape.
Markov Algorithm: It is a type of finite automata used to solve the problems related to formal language theory.
2-way finite automata: It is a type of finite automata in which the head of the tape can move both left and right directions.
Probabilistic Finite State Machine (PFSM): It is a type of finite automata that assigns a probability of each transition.
Quantum Finite Automata (QFA): It is a type of finite automata that uses quantum bits to store and process data.
Weighted Finite State Transducer (WFST): It is a type of finite automata that assigns a weight to each transition which helps in language modeling and speech recognition.
Cellular Automata: It is a type of finite automata in which the grid of cells is used, and each cell follows predefined rules to change its state.
"It is an abstract machine that can be in exactly one of a finite number of states at any given time."
"The FSM can change from one state to another in response to some inputs; the change from one state to another is called a transition."
"Finite-state machines are of two types—deterministic finite-state machines and non-deterministic finite-state machines."
"For any non-deterministic finite-state machine, an equivalent deterministic one can be constructed."
"The behavior of state machines can be observed in many devices in modern society that perform a predetermined sequence of actions depending on a sequence of events with which they are presented."
"Simple examples are: vending machines, which dispense products when the proper combination of coins is deposited."
"Elevators, whose sequence of stops is determined by the floors requested by riders."
"Traffic lights, which change sequence when cars are waiting."
"Combination locks, which require the input of a sequence of numbers in the proper order."
"The finite-state machine has less computational power than some other models of computation such as the Turing machine."
"This is because an FSM's memory is limited by the number of states it has."
"and always has to move from left to right."
"FSMs are studied in the more general field of automata theory."
"Finite-state machine (FSM) or finite-state automaton (FSA, plural: automata)."
"The change from one state to another is called a transition."
"An FSM is defined by a list of its states, its initial state, and the inputs that trigger each transition."
"Deterministic finite-state machines."
"The FSM can change from one state to another in response to some inputs."
"The computational power distinction means there are computational tasks that a Turing machine can do but an FSM cannot."