Question

Suppose that \({\bf{M = }}\left( {{\bf{S,I,f,}}{{\bf{s}}_{\bf{0}}}{\bf{,F}}} \right)\)is a deterministic finite-state machine. Show that if x and y are two strings in \({\bf{I*}}\) that are distinguishable with respect to \({\bf{L}}\left( {\bf{M}} \right)\), then \({\bf{f}}\left( {{{\bf{s}}_{\bf{0}}}{\bf{,x}}} \right) \ne {\bf{f}}\left( {{{\bf{s}}_{\bf{0}}}{\bf{,y}}} \right)\).

Short answer

Therefore,x and y are two strings in \({\bf{I*}}\) that are distinguishable with respect to \({\bf{L}}\left( {\bf{M}} \right)\), then \({\bf{f}}\left( {{{\bf{s}}_{\bf{0}}}{\bf{,x}}} \right) \ne {\bf{f}}\left( {{{\bf{s}}_{\bf{0}}}{\bf{,y}}} \right)\)is proved as true.

Step-by-step solution

General form

Finite-state automaton (Definition): A finite-state automaton \({\bf{M = }}\left( {{\bf{S,I,f,}}{{\bf{s}}_{\bf{0}}}{\bf{,F}}} \right)\) consists of a finite set S of states, a finite input alphabet I, a transition function f that assigns the next state to every pair of states and input (so that \({\bf{f:S \times I}} \to {\bf{S}}\)), an initial or start state \({{\bf{s}}_0}\), and a subset F of S consisting of final (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 recognise 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\}\). It says thatthe strings \({\bf{x}} \in {\bf{I*}}\) and \({\bf{y}} \in {\bf{I*}}\) are distinguishable with respect to L if \(\frac{{\bf{L}}}{{\bf{x}}} \ne \frac{{\bf{L}}}{{\bf{y}}}\). A string z for which \({\bf{xz}} \in {\bf{L}}\) but \({\bf{yz}} \notin {\bf{L}}\), or \({\bf{xz}} \notin {\bf{L}}\), but \({\bf{yz}} \in {\bf{L}}\) is said to distinguishxand y with respect to L.

Concept of indistinguishable with respect to L:

When \(\frac{{\bf{L}}}{{\bf{x}}}{\bf{ = }}\frac{{\bf{L}}}{{\bf{y}}}\), it says that x and y are indistinguishable with respect to L.

Step 2: Proof of the given statement

Given that,\({\bf{M = }}\left( {{\bf{S,I,f,}}{{\bf{s}}_{\bf{0}}}{\bf{,F}}} \right)\) is a deterministic finite-state machine.

To prove: If x and y are two strings in \({\bf{I*}}\) that are distinguishable with respect to \({\bf{L}}\left( {\bf{M}} \right)\), then \({\bf{f}}\left( {{{\bf{s}}_{\bf{0}}}{\bf{,x}}} \right) \ne {\bf{f}}\left( {{{\bf{s}}_{\bf{0}}}{\bf{,y}}} \right)\).

Refer the concept of distinguishable and indistinguishable with respect to L.

Proof:

Let x and y are distinguishable with respect to \({\bf{L}}\left( {\bf{M}} \right)\). As a result, \(\frac{{{\bf{L}}\left( {\bf{M}} \right)}}{{\bf{x}}} \ne \frac{{{\bf{L}}\left( {\bf{M}} \right)}}{{\bf{y}}}\).

By the definition of \(\frac{{{\bf{L}}\left( {\bf{M}} \right)}}{{\bf{x}}}\), there exist a string z such that \({\bf{z}} \in \frac{{{\bf{L}}\left( {\bf{M}} \right)}}{{\bf{x}}}\) and \({\bf{z}} \notin \frac{{{\bf{L}}\left( {\bf{M}} \right)}}{{\bf{y}}}\) (if not, the interchange x and y). or equivalently, \({\bf{xz}} \in {\bf{L}}\left( {\bf{M}} \right)\) and \({\bf{yz}} \notin {\bf{L}}\left( {\bf{M}} \right)\).

Let us consider, for the sake of conflict, that \({\bf{f}}\left( {{{\bf{s}}_{\bf{0}}}{\bf{,x}}} \right){\bf{ = f}}\left( {{{\bf{s}}_{\bf{0}}}{\bf{,y}}} \right)\).

Thereby suggesting that the strings x and y both ends in same state \({\bf{s}}\). However, the strings \({\bf{xz}}\) and \({\bf{yz}}\) should then also end in the same state t (as z starts in the state \({\bf{s}}\) in both cases).

So, that \({\bf{xz}} \in {\bf{L}}\left( {\bf{M}} \right)\) while \({\bf{yz}} \in {\bf{L}}\left( {\bf{M}} \right)\),or \({\bf{xz}} \notin {\bf{L}}\left( {\bf{M}} \right)\) while\({\bf{yz}} \notin {\bf{L}}\left( {\bf{M}} \right)\). It has then obtained a contradiction as \({\bf{xz}} \in {\bf{L}}\left( {\bf{M}} \right)\) and \({\bf{yz}} \notin {\bf{L}}\left( {\bf{M}} \right)\) needs to be true.

As the result, that our assumption \({\bf{f}}\left( {{{\bf{s}}_{\bf{0}}}{\bf{,x}}} \right){\bf{ = f}}\left( {{{\bf{s}}_{\bf{0}}}{\bf{,y}}} \right)\) is incorrect and so, \({\bf{f}}\left( {{{\bf{s}}_{\bf{0}}}{\bf{,x}}} \right) \ne {\bf{f}}\left( {{{\bf{s}}_{\bf{0}}}{\bf{,y}}} \right)\) needs to be true.

Hence, the statement is proved as true.