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
  • 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

Free Tool: ZipGrep

ZipGrep is a utility that can list and search zip (.war, .ear, .jar, etc) archives for text patterns, without the need to extract the archive's contents.

One of a set of tools we're offering as a way to say thank you for being a part of the community.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
math problem distance of x 24 240
Storing historical updates in a database 9 127
directed graph traversal 7 73
InputBaseN() returns different value in ColdFusion 10 and CF2016 5 108
This algorithm (in C#) will resize any image down to a given size while maintaining the original aspect ratio. The maximum width and max height are both optional but if neither are given, the original image is returned. This example is designed t…
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.…

861 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