Lecture No. 19
Dated: 02-01-2025
Memory Required to Recognize a Language
It refers to the amount of information an automaton1 must store at any given time to determine whether a string belongs to the language.
Example
Let \(L_{20}\) be a language1 of strings with length equal to or greater than \(20\), defined over \(\Sigma = \{a, b\}\).
Then, the total number of states required is
Distinguishable Strings
Two strings1 \(x\) and \(y\), belonging to \(\Sigma^*\) are considered distinguishable with respect to \(L \subseteq \Sigma^*\) if there exists \(z \in \Sigma^*\) such that \(xz \in L\) but \(yz \notin L\) or \(yz \in L\) but \(xz \notin L\).
Example
Let \(L\) be a language1 of strings1 defined over \(\Sigma = \{0, 1\}\) such that they end in \(01\).
The strings1 \(110\) and \(010011\) are distinguishable with respect to \(L\) as there exists \(1 \in \Sigma^*\) such that \(1101\) belongs to \(L\) but \(010011\) doesn't belongs to \(L\).
Indistinguishable Strings
Two strings1 \(x\) and \(y\), belonging to \(\Sigma^*\) are considered indistinguishable with respect to \(L \subseteq \Sigma^*\) if there exists \(z \in \Sigma^*\) such that either \(xz \in L\) and \(yz \in L\) or \(xz \notin L\) and \(yz \notin L\).
Example
Let \(L\) be a language1 of strings1 defined over \(\Sigma = \{0, 1\}\) such that they end in \(01\).
The strings1 \(111\) and \(010011\) are indistinguishable with respect to \(L\) as there exists \(1 \in \Sigma^*\) such that both \(1111\) and \(0100111\) don't belongs to \(L\).
Theorem
If \(L\) is a language1 defined over \(\Sigma\) and there are \(n\) strings1 from \(\Sigma^*\) such that any two are distinguishable strings with respect to language1 \(L\) then any finite automaton2 which recognizes \(L\) must have at least \(n\) states.
There may not exist any finite automaton2 which recognizes \(L\).
Proof
Let \(S\) be a set3 of strings1 with respect to language1 \(L\) and contains two strings1 such that they are distinguishable.
Let \(F\) be a finite automaton2 which recognizes \(L\).
Because the strings1 are distinguishable, each should end at different state of \(F\).
This will prove that if we have \(n\) different strings1 then there will be \(n\) different states where each of them will end.
Contradiction
Let's assume that any two or more strings1 end in same state.
This violates the fact that they are distinguishable, hence proving that there has to be \(n\) states.