0

Let $\Sigma = \{0,1\}$ and $w$ be the string $0011101$ over $\Sigma$.

If we work out what $w$ is, $w$ is the binary representation of $57$, which is not prime.

It is remarked in Introduction to Automata Theory, Languages, and Computation, by Hopcroft, Motwani and Ullman, that $w$ cannot be the representation of a prime because

"...every integer except $0$ has a binary representation that begins with $1$."

And I fail to follow the reasoning. Could someone knock the rocks in my head back into place? Thanks!

roo
  • 5,598
  • 1
    $w$ is the binary representation of $29$. – Brian M. Scott Jan 04 '16 at 23:55
  • I would need to dig my copy out, the old hard one or the dumbed down newer one. This makes no sense this way. All primes, except 2 are odd so the 1 bit, wherever it sits, should be set. – mvw Jan 04 '16 at 23:58
  • If the normalization is applied, such that leading 0 digits are dropped, then all positive integers start with a 1 digit. – mvw Jan 05 '16 at 00:01
  • @BrianM.Scott: Perhaps roo forgot an extra $0$ before the final $1$. – Brian Tung Jan 05 '16 at 00:27
  • @mvw: Hard to see how that shows that $111001$ isn't prime, though. :-) – Brian Tung Jan 05 '16 at 00:31
  • "Every integer except 0 has a representation beginning with 1" is exactly the same reasoning that "every integer except 0 has a representation beginning with 1-9". It has nothing to do with primes but just that the integers don't have leading zeros. Except in this computer age we fill bytes with leading zeros all the the time. – fleablood Jan 05 '16 at 00:31
  • It doesn't. 11101 = 29 is prime but 11011 = 27 which isn't. There's nothing in leading 0s that has anything to indicate anything about primeness. The only thing is xxx0 is even and thus not prime unless 10. So all primes end in 1. Which is equivalent to an primes in decimal end in 1,3,7,or 9 if p > 5. – fleablood Jan 05 '16 at 00:36
  • Missing information: 1. Normalized words or fixed width words (for what width?) 2. What end sits $2^0$, left or right? 3. More context for the statement on prime numbers. – mvw Jan 05 '16 at 00:39
  • 1
    Okay, I looked it up online I don't think is is talking about binary numbers at all. He seems to be talking about "languages" to form string and this is a language that forms strings that start with some (maybe none) 0s and at least an equal number of 1's 0011101 is in this language. So is 11101. But 01011 is not. 0011101 is not a prime integer because it isn't an integer at all. 11101 is and integer and it may or may not be prime. 00111101 is not 29 nor 57. It simply isn't an integer at all. But, to be honest, I don't really understand this very much at all. – fleablood Jan 05 '16 at 00:49
  • "2. {0 l V | 0 < i < j}. This language consists of strings with some O's (possibly none) followed by at least as many l's.

    decision is easy. For instance, 0011101 cannot be the representation of a prime, for the simple reason that every integer except 0 has a binary representation that begins with 1. However, it is less obvious whether the string 11101 belongs to L p , so any solution to this problem will have to use significant computational resources of some kind: time and/or space, for example. "

     – fleablood Jan 05 '16 at 00:50
  • Thanks for all the comments. Indeed my conversion of the given number was false. – roo Jan 05 '16 at 17:55

4 Answers4

1

I think it's likely a mistake, although I don't see any mention in the errata.

Perhaps he means every prime except 2 when expressed as a binary digit ends with a 1?

CommonerG
  • 3,273
1

Not sure what the book has in mind there. Perhaps there is a line missing? Is it possible to give a bit more context than you have so far?

Anyway, some remarks about divisibility for binary numbers: A binary number is divisible by $3$ (i.e., $11_2$) iff the number of even-indexed $1$'s and the number of odd-indexed $1$'s are equivalent modulo $3$. Thus, for instance, $57 = 111001_2$ is divisible by $3$, because there are two even-indexed $1$'s and two odd-indexed $1$'s. $2 \equiv 2 \pmod 3$ (trivially), so this number is divisible by $3$.

Note that this is not true of $29 = 11101_2$, which has one even-indexed $1$ and three odd-indexed $1$'s. This doesn't, however, show that $29$ is a prime, although obviously it happens to be. The first counterexample is $5^2 = 25 = 11001_2$, which has one even-indexed $1$ and two odd-indexed $1$'s, but is obviously composite.

Brian Tung
  • 34,160
1

Okay. I found the text online and this is my interpretation.

However the formatting was hard to read, a page or two seems to be missing, and it's a subject I have never studied not even an iota....

but... I think

He's talking about writing a string parser. You give it a binary string and the program is supposed to analyze whether the string is member of a described set. The set could be ... anything. Lp would be the set of prime numbers. But Lc would be the set of valid C programs. I imagine other sets could be capital cities transposed to binary strings but I could be misunderstanding.

So, I think he is saying sometimes it's easy for the program to recognize if a string is a member of a set. If the set is of strings that start with "010" it'd be trivial. Sometimes it is hard. My understanding is if the set is Lc terminating C programs the only way to tell is to actually run it. (Again, I have never studied this field so I might just have said something utterly idiotic and stupid.) So he's saying (I think) the set of Lp is sometimes easy: If the string begins with a 0 then the string isn't an integer at all and can not be a prime. But if the string begins with a 1 and is therefore an integer, there isn't necessarily any easy way to tell if a number is prime.

That's what I think he is saying. 0011101 is not a number therefore not prime. But 11101 is 29 which... we have to do some programming to determine if it is prime simply by looking at it.

I think.

Excerpt:

============

"32 CHAPTER 1. AUTOMATA: THE METHODS AND THE MADNESS

Set-Formers as a Way to Define Languages

It is common to describe a language using a "set-former" :

{w | something about w)

This expression is read "the set of words w such that (whatever is said about w to the right of the vertical bar}." Examples are:

1 . {vj | w consists of an equal number of O's and 1 's } .

  1. {w | w is a binary integer that is prime }.

  2. {w J id is a syntactically correct C program }.

It is also common to replace w by some expression with parameters and describe the strings in the language by stating conditions on the parame- ters. Here are some examples; the first with parameter n, the second with parameters i and j:

  1. {0™1" | n > 1}. Read "the set of 0 to the n 1 to the n such that n is greater than or equal to 1," this language consists of the strings {01,0011,000111,...}. Notice that, as with alphabets, we can raise a single symbol to a power n in order to represent n copies of that symbol.

  2. {0 l V | 0 < i < j}. This language consists of strings with some O's (possibly none) followed by at least as many l's.

...*page missing????....

decision is easy. For instance, 0011101 cannot be the representation of a prime, for the simple reason that every integer except 0 has a binary representation that begins with 1. However, it is less obvious whether the string 11101 belongs to L p , so any solution to this problem will have to use significant computational resources of some kind: time and/or space, for example. □

One potentially unsatisfactory aspect of our definition of "problem' 7 is that one commonly thinks of problems not as decision questions (is or is not the following true?) but as requests to compute or transform some input (find the best way to do this task). For instance, the task of the parser in a C compiler can be thought of as a problem in our formal sense, where one is given an ASCII string and asked to decide whether or not the string is a member of L c , the set of valid C programs. However, the parser does more than decide. It produces a parse tree, entries in a symbol table and perhaps more. Worse, the compiler as a whole solves the problem of turning a C program into object code for some "

fleablood
  • 124,253
0

There is no mistake and the meaning is clear. However, it might have been simpler to state that $0011101$ is not the binary representation of any number (prime or not) because except for $0$, the binary representation of a number always start by $1$.

Let me quote the whole paragraph:

The problem of testing primality can be expressed by the language $L_P$ consisting of all binary strings whose values as a binary number is prime. That is, given a string of $0$'s and $1$'s, say "yes" if the string is the binary representation of a prime and say "no" if not. For some strings, this decision is easy. For instance, $0011101$ cannot be the representation of a prime, for the simple reason that every integer except $0$ has a binary representation that begins with $1$. However, it is less obvious whether the string $11101$ belongs to $L_P$, so any solution to this problem will have to use significant computational resources of some kind: time and/or space, for example.

J.-E. Pin
  • 40,163
  • Thanks for answering the question. Perhaps I would have seen it more clearly if I would have correctly converted 11101 to binary. :) – roo Jan 05 '16 at 17:52