The Benford-Newcomb distribution and unambiguous context-free languages. (English) Zbl 1156.68035

Ravikumar, Bala

Int. J. Found. Comput. Sci. 19, No. 3, 717-727 (2008).

Summary: For a string \(w\in\{0,1,2,\dots, d-1\}^*\), let \(\text{val}_d(w)\) denote the integer whose base \(d\) representation is the string \(w\) and let \(\text{MSD}_d(x)\) denote the most significant or the leading digit of a positive integer \(x\) when \(x\) is written as a base \(d\) integer. M. Hirvensalo and J. Karhumäki [“Computing partial information out of intractable one – the first digit of \(2^n\) at base \(3\) as an example”, Lect. Notes Comput. Sci. 2420, 319–327 (2002; Zbl 1023.11062)] studied the problem of computing the leading digit in the ternary representation of \(2^x\) and showed that this problem has a polynomial time algorithm. Some applications were presented for the problem of computing the leading digit of \(A^B\) for given inputs \(A\) and \(B\). In this paper, we study this problem from a formal language point of view. Formally, we consider the language \(L_{b,d,j} = \{w\mid w \in \{0,1,2,\dots, d-1\}^*\), \(1\leq j\leq 9\), \(\text{MSD}_b(d^{\text{val}_b(w)})) = j\}\) (and some related classes of languages) and address the question of whether this and some related languages are context-free. Standard pumping lemma proofs seem to be very difficult for these languages. We present a unified and simple combinatorial technique that shows that these languages are not unambiguous context-free languages. The Benford-Newcomb distribution plays a central role in our proofs.

MSC:

68Q45

Formal languages and automata

Keywords:

density; Weyl’s theorem

Citations:

Zbl 1023.11062

References:

[1]	Berger A., Trans. Amer. Math. Soc 457 pp 197–
[2]	Borwein J., Mathematics by Experiment (2003)
[3]	Diaconis P., Annals of Probability pp 72–
[4]	DOI: 10.1007/978-1-4613-0015-1 · doi:10.1007/978-1-4613-0015-1
[5]	Hardy G. H., An introduction to the theory of numbers (1979) · Zbl 0423.10001
[6]	Hopcroft J., Introduction to Automata, Formal Languages and Theory Computation (1979) · Zbl 0426.68001
[7]	Hill T., Proc. of the American Mathematical Society 123 pp 887–
[8]	Hill T., Chance 26 pp 8–
[9]	Kemp R., Acta Informatica pp 295–
[10]	Kuipers L., Uniform Distribution of Sequences (1974) · Zbl 0281.10001
[11]	Knuth D., The Art of Computer Programming, Volume 2: Semi-Numerical Algorithms (1998) · Zbl 0895.65001
[12]	DOI: 10.2307/2319349 · Zbl 0349.60014 · doi:10.2307/2319349
[13]	Ravikumar B., Information Processing Letters 105 pp 131–
[14]	Rosen K., Elementary Number Theory and Its Applications (2005)
[15]	Stinson D., Cryptography Theory and Practice (1995) · Zbl 0855.94001