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:

    Science and technology multiply around us. To an increasing extent they dictate the languages in which we speak and think. Either we use those languages, or we remain mute.
    —J.G. (James Graham)