Finite-state automaton (Definition):A finite-state automata \({\bf{M = }}\left( {{\bf{S,I,f,}}{{\bf{s}}_{\bf{0}}}{\bf{,F}}} \right)\) consists of an initial or start state \({{\bf{s}}_0}\), a finite set S of states, a finite alphabet of inputs I, a transition function f that assigns a subsequent state to each pair of states and inputs (such that \({\bf{f:S \times I}} \to {\bf{S}}\)), and a subset F of S made up of final states (or accepting states).
Regular expressions (Definition):A recursive definition of the regular expressions over a set I is as follows:
A regular expression is the symbol \(\emptyset \);
A regular expression is the symbol \({\bf{\lambda }}\);
When \({\bf{x}} \in {\bf{I}}\) occurs, the symbol x is a regular expression.
When A and B are regular expressions, the symbols \(\left( {{\bf{AB}}} \right){\bf{,}}\left( {{\bf{A}} \cup {\bf{B}}} \right){\bf{,}}\) and \({\bf{A*}}\) are also regular expressions.
Regular sets are the sets that regular expressions represent.
Kleene’s theorem: A finite-state automaton must recognize a set-in order for it to be considered regular.
Theorem 2:If and only if it is a regular set, a set is produced by a regular grammar.
Concept of distinguishable with respect to L:
Suppose that L is a subset of \({\bf{I*}}\), where \({\bf{I}}\) is a nonempty set of symbols. If \({\bf{x}} \in {\bf{I*}}\), let \(\frac{{\bf{L}}}{{\bf{x}}}{\bf{ = }}\left\{ {{\bf{z}} \in {\bf{I*}}\left| {{\bf{xz}} \in {\bf{L}}} \right.} \right\}\). If \(\frac{{\bf{L}}}{{\bf{x}}} \ne \frac{{\bf{L}}}{{\bf{y}}}\), thenthe strings \({\bf{x}} \in {\bf{I*}}\) and \({\bf{y}} \in {\bf{I*}}\) can be distinguished from one another with respect to L.
A string z is said to distinguish x and y with respect to L if \({\bf{xz}} \in {\bf{L}}\) but \({\bf{yz}} \notin {\bf{L}}\), or \({\bf{xz}} \notin {\bf{L}}\), but \({\bf{yz}} \in {\bf{L}}\).
Concept of indistinguishable with respect to L:
If\(\frac{{\bf{L}}}{{\bf{x}}}{\bf{ = }}\frac{{\bf{L}}}{{\bf{y}}}\), then x and y are said to be indistinguishable from L.
