Probabilistic Automaton - p-adic Languages

p-adic Languages

The p-adic languages provide an example of a stochastic language that is not regular, and also show that the number of stochastic languages is uncountable. A p-adic language is defined as the set of strings in the letters such that

L_{\eta}(p)=\{0.n_1n_2n_3 \ldots \vert 0\le n_k<p \text{ and }
0.n_1n_2n_3\ldots > \eta \}

That is, a p-adic language is merely the set of real numbers, written in base-p, such that they are greater than . It is straightforward to show that all p-adic languages are stochastic. However, a p-adic language is regular if and only if is rational. In particular, this implies that the number of stochastic languages is uncountable.

Read more about this topic:  Probabilistic Automaton

Famous quotes containing the word languages:

    No doubt, to a man of sense, travel offers advantages. As many languages as he has, as many friends, as many arts and trades, so many times is he a man. A foreign country is a point of comparison, wherefrom to judge his own.
    Ralph Waldo Emerson (1803–1882)