Myhill-Nerode's theorem

The Myhill-Nerode are in field formal languages of theoretical computer science , a necessary and sufficient criterion for that a formal language regularly is. It was presented and proven in 1957/1958 by John Myhill and Anil Nerode .

In colloquial terms, the sentence is mainly used to find out whether a formal language is so "benign" or "simply knitted" that a computer with constant memory (ie with finite memory, the size of which does not depend on the input) can automatically determine whether a character string is a word of the language or not.

sentence

Note: The following technical terms are explained in the article Formal Language .

A formal language above the alphabet and the associated Nerode relation are given . Then: ${\ displaystyle L}$ ${\ displaystyle \ Sigma}$ ${\ displaystyle \ sim}$

There is a deterministic finite automaton that accepts if and only if the index of the associated Nerode relation is finite. ${\ displaystyle L}$

Formally:

{\ displaystyle \ exists A: \ L (A) = L \ qquad \ Longleftrightarrow \ qquad | \ Sigma ^ {*} / \ sim | <\ infty}

where is a deterministic finite automaton and the language it accepts. ${\ displaystyle A}$ ${\ displaystyle L (A)}$

application

The existence of a deterministic finite automaton that accepts is a necessary and sufficient criterion for being a regular language. The sentence can be used both to show that a formal language is regular and to show that it is not. Since this is the most important application of Myhill-Nerode's theorem, it is often read like this: ${\ displaystyle L}$ ${\ displaystyle L}$

The language is regular if and only if the index of the associated Nerode relation is finite. ${\ displaystyle L}$

It can further be concluded that the number of states of a minimal deterministic finite automaton that accepts corresponds to the index of the associated Nerode relation. ${\ displaystyle L}$

More precisely: Let be a system of representatives of , then is the (unique) minimal, deterministic automaton that accepts, where ${\ displaystyle W = \ {w_ {i}, \ ldots \}}$ ${\ displaystyle \ Sigma ^ {*} / \ sim}$ ${\ displaystyle {\ mathcal {A}} = (Q, \ Sigma, \ delta, q_ {0}, F)}$ ${\ displaystyle L}$

${\ displaystyle Q = \ Sigma ^ {*} / \ sim}$ The states correspond to the equivalence classes ${\ displaystyle \ sim}$
${\ displaystyle q_ {0} = [\ epsilon] _ {\ sim}}$ The start state corresponds to the equivalence class in which the empty word is located
${\ displaystyle F = \ {[w_ {i}] _ {\ sim} \ mid w_ {i} \ in L \}}$ Final states correspond to the equivalence classes of the words that lie in (conversely, it decays exactly into the equivalence classes that lie in, i.e. ) ${\ displaystyle L}$ ${\ displaystyle L}$ ${\ displaystyle F}$ ${\ displaystyle L = \ bigcup F}$
${\ displaystyle \ delta ([w_ {i}] _ {\ sim}, a) = [w_ {i} \ cdot a] _ {\ sim}}$ for all ${\ displaystyle w_ {i} \ in W, a \ in \ Sigma}$

This relationship also applies to non-regular languages. There it is not finite, which means that (due to the minimality of ) there is no DEA for . ${\ displaystyle Q}$ ${\ displaystyle {\ mathcal {A}}}$ ${\ displaystyle L}$

Another application is that with the help of the theorem it can be proven that (independent of the P-NP problem ) there is no polynomial time algorithm that constructs an equivalent DEA from an NEA. There are languages that are recognized by an NEA with states, but which have Myhill-Nerode equivalence classes. ${\ displaystyle n + 1}$ ${\ displaystyle 2 ^ {n}}$

An example of this is the language. If two words are of different length , then they differ in one position . So exactly one of the words and is in and it applies . ${\ textstyle L_ {n} = \ {w \ in \ {0,1 \} ^ {*} \ mid {\ text {in the}} n {\ text {-last position of}} w {\ text { there is a 0}} \}.}$ ${\ displaystyle w_ {1}, w_ {2}}$ ${\ displaystyle \ {0.1 \} ^ {*}}$ ${\ displaystyle n}$ ${\ displaystyle i}$ ${\ displaystyle w_ {1} 0 ^ {i-1}}$ ${\ displaystyle w_ {2} 0 ^ {i-1}}$ ${\ displaystyle L_ {n}}$ ${\ displaystyle [w_ {1}] _ {\ sim} \ neq [w_ {2}] _ {\ sim}}$

So the output can be exponentially larger than the input and so no Turing machine can calculate the output in less than exponential time. There is therefore no better algorithm for this problem than the power set construction .

Examples

Finite languages are regular

The language above the alphabet contains a finite number of words. (All words from have finite length.) That is, there exist natural numbers and , so that: ${\ displaystyle L}$ ${\ displaystyle \ Sigma}$ ${\ displaystyle L}$ ${\ displaystyle m}$ ${\ displaystyle n}$

${\ displaystyle | L | \ leq m}$
${\ displaystyle | w | \ leq n \ quad \ forall w \ in L}$ .

Since there are as many prefixes for every word as there are letters and the empty word also counts as a prefix, the language has at most prefixes and as many equivalence classes. The following applies: ${\ displaystyle \ epsilon}$ ${\ displaystyle L}$ ${\ displaystyle n \ cdot m + 1}$

{\ displaystyle \ operatorname {ind} (L) \ leq n \ cdot m + 1 <\ infty}

.

That is, the number of equivalence classes is finite, and it follows from Myhill-Nerode's theorem that the language is regular. So you can say: every language that contains a finite number of words is regular. ${\ displaystyle L}$

The language { ε , a , aa , aaa , ...} is regular

A minimal deterministic finite automaton that accepts language .

{\ displaystyle \ {a \} ^ {*}}

The language above the alphabet is defined by: ${\ displaystyle L}$ ${\ displaystyle \ Sigma: = \ {a \}}$

{\ displaystyle L: = \ {a \} ^ {*}}

.

There is exactly one equivalence class with regard to the Nerode relation, namely itself: ${\ displaystyle L}$

{\ displaystyle [\ epsilon] = [a] = [aa] = [aaa] = \ ldots = \ {\ epsilon, a, aa, aaa, \ dotsc \} = \ {a \} ^ {*} = L }

.

This means that all prefixes of the language can be supplemented with the same suffixes for words . So the index of the Nerode relation is finite: ${\ displaystyle L}$ ${\ displaystyle L}$

{\ displaystyle \ operatorname {ind} (L) = 1 <\ infty}

.

Finally, it follows from Myhill-Nerode's theorem that the language is regular. ${\ displaystyle L}$

The language { ab , aabb , aaabbb , ...} is not regular

Section of a non-finite, deterministic automaton that accepts the formal language L. Each of the infinitely many words from L needs its own path to the final state, so the automaton would have to be infinitely large.

The language above the alphabet is defined by: ${\ displaystyle L}$ ${\ displaystyle \ Sigma: = \ {a, b \}}$

{\ displaystyle L: = \ {a ^ {n} b ^ {n} \ mid n \ in \ mathbb {N}, n> 0 \}}

.

In particular, the following equivalence classes result with regard to the Nerode relation (each prefix of a word in this language allows only one suffix for completion):

{\ displaystyle {\ begin {matrix} & [ab] & = & L & \ mathrm {Suffix:} & \ {\ epsilon \} \\ & [a ^ {2} b] & = & \ {a ^ {2} b, a ^ {3} b ^ {2}, a ^ {4} b ^ {3}, \ ldots \} & \ mathrm {Suffix:} & \ {b \} \\ & [a ^ {3} b] & = & \ {a ^ {3} b, a ^ {4} b ^ {2}, a ^ {5} b ^ {3}, \ ldots \} & \ mathrm {Suffix:} & \ { bb \} \\ & \ vdots && \ vdots \\ & [a ^ {k} b] & = & \ {a ^ {k + i-1} b ^ {i} \ mid k, i \ geq 1 \ in \ mathbb {N} \} & \ mathrm {Suffix:} & \ {b ^ {k-1} \} \\ & \ vdots && \ vdots \ end {matrix}}}

These equivalence classes differ in pairs , that is, the following applies:

{\ displaystyle [a ^ {i} b] \ neq [a ^ {j} b] \ quad \ forall i, j \ in \ mathbb {N}: i \ neq j}

.

From this it follows that the number of these equivalence classes is already infinite and - since the number of all equivalence classes is even larger - the index of the Nerode relation is also infinite. Finally, it follows from Myhill-Nerode's theorem that the language is not regular. ${\ displaystyle L}$ ${\ displaystyle L}$ ${\ displaystyle L}$

comment

It is not necessary to fully explain the class structure of the equivalence relation assigned to a language in order to show the non-regularity of this language. Otherwise, further equivalence classes would have to be set up in order to meet the requirement of equivalence relations, to completely subdivide a certain basic set (here :, i.e. all words above the input alphabet ) into disjoint equivalence classes. ${\ displaystyle L}$ ${\ displaystyle \ Sigma ^ {*}}$ ${\ displaystyle \ Sigma}$

The suffixes

In principle, any word above the input alphabet can be used as a suffix , e.g. B. etc. Here only the single suffix was given for each equivalence class, for which, when it is added to the elements of the respective class, all words created in this way belong to the language . For any other suffix, any resulting words would not belong to the language . The Nerode relation is based on this . ${\ displaystyle \ Sigma}$ ${\ displaystyle a, b, abab, aabbaba}$ ${\ displaystyle L}$ ${\ displaystyle L}$

literature

Uwe Schöning : Theoretical Computer Science - in a nutshell . 5th edition. Spektrum, Heidelberg 2008, ISBN 978-3-8274-1824-1 , ( HochschulTaschenbuch ), pp. 34-38.
A. Nerode: Linear automaton transformations . In: Proceedings of the American Mathematical Society 9, 1958, ISSN 0002-9939 , pp. 541-544.
J. Myhill: Finite automata and the representation of events . In: WADD TR 57-624, 1957, ZDB -ID 2518731-4 , pp. 112-137.

Myhill-Nerode's theorem

contents

sentence

application