Solved

Is the following solution for pairwise disjointment correct?

Posted on 2008-10-06
5
999 Views
Last Modified: 2012-08-14
Experts,

Below I have the following grammer and needed to perform pairwise disjointment. From what I understand I need to calculate the first sets. For each rule find each first letter could be in a
string and use that rule. A sing non-terminal should not have two rules that start
with the same terminal.

Do I have the following correct? And is the fix correct?
A - aB | b | cBB

B -aB |bA |aBb

C- aaA |b|caB

 


 

A= a|b|c

B=a|b|a    **not acceptable

C=a|b|c

 

To Fix:

B = aY

Y=B|Bb
0
Comment
Question by:missymadi
  • 3
  • 2
5 Comments
 
LVL 45

Expert Comment

by:sunnycoder
Comment Utility
> pairwise disjointment.
Can you explain in more detail what you are trying to achieve? This is the first time I heard that term :)

Are you trying to construct a CFG or a regular grammar or something else? What is the language supposed to express?
0
 

Author Comment

by:missymadi
Comment Utility
For example:
<S> ::= <A> a <B> b
<A> ::= <A> b | b
<B> ::= a <B> | a

S- there would be no conflict because <S> only has one rule for associated with it. However, look at <A> there is a potential infinite loop.

I was wondering if I'm understanding this correctly by my previous question and answer.

Thanks, MissyMadi
0
 
LVL 45

Expert Comment

by:sunnycoder
Comment Utility
1.
Ummm ... if you successfully remove the infinite loop, wont you change the language?
e.g.
<S> ::= <A> a <B> b
<A> ::= <A> b | b
<B> ::= a <B> | a

This would accept    bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbaab
In fact you can add infinite number of b to the string of b and it can still be expressed by the grammar. However, if you remove the loop, you would not be able to express strings like one above.

2.
To Fix:

B = aY

Y=B|Bb

You have not removed the loop but simply spread it over two statements ...

B = aY = aB = aaY = aaB = aaaY ...

This most likely is part of some course that you are taking. If you can give me exact problem statement, may be I can help you better.
0
 

Author Comment

by:missymadi
Comment Utility
Yes, this is one of the question from the course book that stumped me.

Here's the question:
Perform the pairwise disjointness test for the following grammer rules
a. A - aB | b | cBB

b. B -aB |bA |aBb

c. C- aaA |b|caB
0
 
LVL 45

Accepted Solution

by:
sunnycoder earned 125 total points
Comment Utility
Okay .. you are essentially performing the test to identify left recursive grammars.

You are correct in saying that a and c are fine and b fails the test - even though it is not left recursive. Look closely you can change the grammar by adding a followset for combining first and third rule (for B) that would give you unique first set for B

0

Featured Post

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

Article by: Nadia
Linear search (searching each index in an array one by one) works almost everywhere but it is not optimal in many cases. Let's assume, we have a book which has 42949672960 pages. We also have a table of contents. Now we want to read the content on p…
Prime numbers are natural numbers greater than 1 that have only two divisors (the number itself and 1). By “divisible” we mean dividend % divisor = 0 (% indicates MODULAR. It gives the reminder of a division operation). We’ll follow multiple approac…
Internet Business Fax to Email Made Easy - With eFax Corporate (http://www.enterprise.efax.com), you'll receive a dedicated online fax number, which is used the same way as a typical analog fax number. You'll receive secure faxes in your email, fr…
You have products, that come in variants and want to set different prices for them? Watch this micro tutorial that describes how to configure prices for Magento super attributes. Assigning simple products to configurable: We assigned simple products…

744 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

12 Experts available now in Live!

Get 1:1 Help Now