Is the following solution for pairwise disjointment correct?

Posted on 2008-10-06
Last Modified: 2012-08-14

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



To Fix:

B = aY

Question by:missymadi
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 3
  • 2
LVL 45

Expert Comment

ID: 22651272
> 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?

Author Comment

ID: 22651389
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
LVL 45

Expert Comment

ID: 22651543
Ummm ... if you successfully remove the infinite loop, wont you change the language?
<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.

To Fix:

B = aY


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.

Author Comment

ID: 22652340
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
LVL 45

Accepted Solution

sunnycoder earned 125 total points
ID: 22670998
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


Featured Post

[Webinar] Learn How Hackers Steal Your Credentials

Do You Know How Hackers Steal Your Credentials? Join us and Skyport Systems to learn how hackers steal your credentials and why Active Directory must be secure to stop them. Thursday, July 13, 2017 10:00 A.M. PDT

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

One of Google's most recent algorithm changes affecting local searches is entitled "The Pigeon Update." This update has dramatically enhanced search inquires for the keyword "Yelp." Google searches with the word "Yelp" included will now yield Yelp a…
Article by: Nadia
Suppose you use Uber application as a rider and you request a ride to go from one place to another. Your driver just arrived at the parking lot of your place. The only thing you know about the ride is the license plate number. How do you find your U…
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below.…
Monitoring a network: how to monitor network services and why? Michael Kulchisky, MCSE, MCSA, MCP, VTSP, VSP, CCSP outlines the philosophy behind service monitoring and why a handshake validation is critical in network monitoring. Software utilized …

624 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