International Journal of Foundations of Computer Science 19(3), pp. 717-727.
ISSN/ISBN: 0129-0541 DOI: 10.1142/S0129054108005905
Abstract: For a string w ∈ {0,1, 2,..., d-1}*, let vald(w) denote the integer whose base d representation is the string w and let MSDd(x) denote the most significant or the leading digit of a positive integer x when x is written as a base d integer. Hirvensalo and Karhumäki [9] studied the problem of computing the leading digit in the ternary representation of 2x ans showed that this problem has a polynomial time algorithm. In [16], some applications are presented for the problem of computing the leading digit of AB 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 Lb,d,j = {w|w ∈ {0,1, 2,..., d-1}*, 1 ≤ j ≤ 9, MSDb(dvalb(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.
Bibtex:
@article {MR2417964,
AUTHOR = {Ravikumar, Bala},
TITLE = {The {B}enford-{N}ewcomb distribution and unambiguous
context-free languages},
JOURNAL = {Internat. J. Found. Comput. Sci.},
FJOURNAL = {International Journal of Foundations of Computer Science},
VOLUME = {19},
YEAR = {2008},
NUMBER = {3},
PAGES = {717--727},
ISSN = {0129-0541},
MRCLASS = {68Q42 (68Q25 68Q45)},
MRNUMBER = {2417964 (2009h:68068)},
DOI = {10.1142/S0129054108005905},
URL = {http://dx.doi.org/10.1142/S0129054108005905},
}
Reference Type: Journal Article
Subject Area(s): Computer Science