| Re .1:
The reason I wrote lambda is clear if you know the evolution:
The actual Greek letter lambda is used when writing by hand or when the
symbol is available.
Since I was typing, but I was used to lambda, I typed "lambda".
I agree, "empty" would be more clear, but how about """"""? By this, I do
not mean six quotes, but just two; the quoted quotes are doubled. So the
rule S -> lambda would be written:
S -> ""
Of course, it might be even better to write:
S ->
-- edp
|
| Solution:
m n
The following grammar has the language b c , where 2n/5 <= m <= 3n/5.
S -> E
E -> bbEccccc
E -> bbbEccccc
E -> bEcc
E -> lambda
Proof:
It's a simple matter to show by induction that the language contains
m n
only strings b c , with 2n/5 <= m <= 3n/5, since, if (m,n) satistfies
the inequality, then so must (m+2,n+5), (m+3,n+5) and (m+1,n+2).
We must show that all strings satisfying the inequality are produced
by the grammar. Given a string that satisfies the inequality, it can
be produced by applying the productions the following number of times:
S -> E 1
E -> bbEccccc (3n-5m - (3n mod 5))/5
E -> bbbEccccc (5m-2n - (3n mod 5))/5
E -> bEcc 3n mod 5
E -> lambda 1
It is a simple matter to show that this yields the correct number of
b's and c's, but we must still show that the expressions yield non-
negative integers. Clearly, they yield integers, since 3n - (3n mod 5)
and 2n + (3n mod 5) are always multiples of 5.
From 3n >= 5m, we have 3n - (3n mod 5) >= 5m, and so 3n-5m - (3n mod 5)
is always >= 0. Recalling that 2n + (3n mod 5) is always a multiple of 5,
and that 5m >= 2n, we have 5m >= 2n + (3n mod 5), so 5m-2n - (3n mod 5)
is always >=0, too.
Thus, the productions can be applied the described number of times to
m n
yield any string b c that satisfies 2n/5 <= m <= 3n/5. And since the
grammar generates only strings satisfying 2n/5 <= m <= 3n/5, it is a
solution to the problem.
[ Note that from this grammar, it's a simple matter to produce one
which doesn't also admit the production of lambda, by removing the
production E -> lambda, and including the productions: E -> bbccccc,
E -> bbbccccc, and E -> bcc. ]
- Gilbert
|
| That is the answer I found. I like it because it seemed rather difficult when
I started doing the problem, but the answer was really quite simple.
Generalization: Construct a context-free grammar than generates all
m n
strings of the form b c , where p/q <= m/n <= r/s, where
p and r are non-negative integers, and q and s are
positive integers.
Conjecture: The rules:
{ S -> lambda,
u v
S -> b Sc | p/q <= u/v <= r/s and v <= max(q,s) }
form such a grammar (with non-terminal { S }, terminals
{ b, c}, and starting symbol S).
-- edp
|