Fishcake

I'm trying to teach myself about how compilers actually do their job at compiling a programming language into another by reading the Dragon Book. Hopefully, this will help me do scripting for games in the future. I came across some exercises which I couldn't answer. Hopefully, someone is able to to help me, which is most likely the case.

Exercise 2.2.2: What language is generated by the following grammars? In each case justify your answer.

$<math>S \rightarrow 0\ S\ 1\ |\ 0 1</math>$
$<math>S \rightarrow +\ S\ S\ |\ -\ S\ S\ |\ a</math>$
$<math>S \rightarrow S\ (\ S\ )\ S\ |\ \epsilon</math>$
$<math>S \rightarrow \bold{a}\ S\ \bold{b}\ S\ |\ \bold{b}\ S\ \bold{a}\ S\ |\ \epsilon</math>$
$<math>S \rightarrow \bold{a}\ |\ S+S\ |\ S\ S\ |\ S\ *\ |\ (\ S\ )</math>$

For these set of questions, I'm not sure what is it that the question wants. They don't look like context-free grammars for programming languages (if that is what the question wants) to me. I'm not sure how to describe most of them either. I can only describe 2., which I'm pretty sure will produce a prefix arithmetic expression.

Exercise 2.2.5:

Show that all binary strings generated by the following grammar have
values divisible by 3. Hint. Use induction on the number of nodes in a
parse tree.
$<math>\mathit{num} \rightarrow 11\ |\ 1001\ |\ \mathit{num}\ 0\ |\ \mathit{num}\ \mathit{num}</math>$
Does the grammar generate all binary strings with values divisible by 3?

For this one, I'm not sure how to even approach the problem. I only know simple mathematical prove by induction (if it is even relevant to the problem). I can tell that it will always generate a number divisible by 3, but I'm not sure how to go about proving it.

I'll try to keep the thread alive by posting more questions in the future.

mEmO

For 2.2.2, they ask for the set of strings that is accepted by the language. So the first one is "all strings with n 0s followed by n 1s", for instance.

In 2.2.5, I don't see "prove" mentioned anywhere in the exercise. it says show, which is a totally different matter.

Fishcake

Okay, so for 2.2.2, all I need to do is describe the possible output of the grammar.

mEmO said:

In 2.2.5, I don't see "prove" mentioned anywhere in the exercise. it says show, which is a totally different matter.

Hmm.., I always thought that both of them have the same meaning. So how do I actually "show" that all the numbers generated by the grammar is divisible by 3? Just say that since every number generated will start with either 3 or 9, and end with 3, 9, or 0, which makes every possible generated number divisible by 3? What about the "hint" part? I don't actually understand it.

Anyway, thanks for replying!

Shravan

A number is divisible by 3 if the sum of the digits in that number is divisible by 3.

X-G

mEmO said:

So the first one is "all strings with n 0s followed by n 1s", for instance.

All strings with n 0s followed by n 1s, where > 0.

Fishcake said:

For this one, I'm not sure how to even approach the problem.

Well, you have a language where each symbol can be either a constant, a different constant, another symbol followed by a zero, or two symbols concatenated. You'd need to show the following:

That the first constant is divisible by three (trivial)
That the second constant is divisible by three (trivial -- this and the above are your initial conditions)
Prove that if S is divisible by three, then so is "S 0".
Prove that if S is divisible by three, then so is "S S".

The similarity to "ordinary" induction should be evident.

Jakub Wasilewski

Fishcake said:

Hmm.., I always thought that both of them have the same meaning.

They do in the context of a math or CS textbook.

X-G said:

That the first constant is divisible by three (trivial)
That the second constant is divisible by three (trivial -- this and the above are your initial conditions)
Prove that if S is divisible by three, then so is "S 0".
Prove that if S is divisible by three, then so is "S S".

Small correction for the last case: prove that if S and T are both divisible by three, then so is "S T". There is no requirement for S and T to be the same string.

Other than that, it's just like X-G said - you have to prove that starting with a number(s) divisible by 3, there is no production that will make it not divisible by 3.

Shravan said:

A number is divisible by 3 if the sum of the digits in that number is divisible by 3.

This only holds in base 10 (well, to be perfectly correct, also in base 4, 7, 13 and any base that is 3k+1 for k>=1 ). Not that it would help solve the problem if it held in binary.

Fishcake

Thank you for replying guys! It really helped me a lot. I struggled at first, but I found out how to prove it at last. I think it's correct. Here goes my solution. Let me know if it is incorrect, or I forgot something.

My Solution

Any natural number $<math>\mathit{n}</math>$ is divisible by 3 if it can be represented in the form of $<math>\mathit{n} = 3\mathit{m}</math>$ where $<math>\mathit{m}</math>$ is also a natural number less than $<math>\mathit{n}</math>$ .

For the first 2 productions, proving is trivial. $<math>11_2 = 3_{10} = 3(1)</math>$ and $<math>1001_2 = 9_{10} = 3(3)</math>$ , so they are both divisible by 3.

The third production is simply adding 0s to the end of the number. In binary, this is known as left shifting, which is equivalent to multiplying the number with $<math>2^\mathit{n}</math>$ , where $<math>\mathit{n}</math>$ is the number of shifts made. Since $<math>S</math>$ is proven to be divisible by 3, we can say that :

$<math>2^\mathit{n}(S) = 2^\mathit{n}(3\mathit{r}) = 3(2^\mathit{n}\mathit{r})</math>$

So the number is still divisible by 3.

The fourth production is $<math>S \rightarrow S_1\ S_2</math>$ , which has the effect of multiplying $<math>S_1</math>$ by $<math>2^\mathit{n}</math>$ , where $<math>\mathit{n}</math>$ is the number of bits in $<math>S_2</math>$ , and adding the product of the multiplication with $<math>S_2</math>$ . This can be represented with an equation :

$<math>S = 2^\mathit{n}(S_1) + S_2</math>$

Since $<math>S_1</math>$ and $<math>S_2</math>$ are proven to be divisible by 3, we can say that:

$<math>S = 2^\mathit{n}(3\mathit{a}) + 3\mathit{b}</math>$
$<math>S = 3(2^\mathit{n}\mathit{a}) + 3\mathit{b}</math>$
$<math>S = 3(2^\mathit{n}\mathit{a} + \mathit{b})</math>$

Therefore, $<math>S</math>$ is always divisible by 3.

Thread #602679. Printed from Allegro.cc