Re: Exercise 2.1.2 from Aho&Ulman The theory of Parsing textbook?
- From: Barb Knox <see@xxxxxxxxx>
- Date: Tue, 22 Apr 2008 16:50:59 +1200
In article
<0a72f6c4-1337-4884-bb1c-a205b1fef1a3@xxxxxxxxxxxxxxxxxxxxxxxxxxx>,
Tegiri Nenashi <TegiriNenashi@xxxxxxxxx> wrote:
"Construct CFG that generates all strings having equal number of a's
and b's"
My attempt:
X = 1 + aXa + aaX +Xaa + bXb + Xbb +bbX +YY
Y = 1 + (a+b)Y
looks too complicated for such concise problem statement. Any shorter
solution?
The difficulty isn't that it's too complicated, but that it's wrong.
Your Y can be any string of a's and b's; the "YY" alternative in X does
*not* mean that the same Y string is replicated, but rather that 2
independent Y strings are concatenated. So, your X grammar will accept
*any* string of a's and b's (e.g., with the first Y being empty, and the
second being any string of a's and b's).
--
---------------------------
| BBB b \ Barbara at LivingHistory stop co stop uk
| B B aa rrr b |
| BBB a a r bbb | Quidquid latine dictum sit,
| B B a a r b b | altum viditur.
| BBB aa a r bbb |
-----------------------------
.
- Follow-Ups:
- Re: Exercise 2.1.2 from Aho&Ulman The theory of Parsing textbook?
- From: Tegiri Nenashi
- Re: Exercise 2.1.2 from Aho&Ulman The theory of Parsing textbook?
- References:
- Exercise 2.1.2 from Aho&Ulman The theory of Parsing textbook?
- From: Tegiri Nenashi
- Exercise 2.1.2 from Aho&Ulman The theory of Parsing textbook?
- Prev by Date: Re: How can I tell if F is a string or if it is a number?
- Next by Date: Re: Another approach to Decide Solvability of Univariate Integer Polynomials, and a possible Multivariate Extension
- Previous by thread: Re: Exercise 2.1.2 from Aho&Ulman The theory of Parsing textbook?
- Next by thread: Re: Exercise 2.1.2 from Aho&Ulman The theory of Parsing textbook?
- Index(es):
Relevant Pages
|
