Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
Solved

# Is the following solution for pairwise disjointment correct?

Posted on 2008-10-06
Medium Priority
1,007 Views
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
[X]
###### 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
• 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?
0

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.

0

LVL 45

Expert Comment

ID: 22651543
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

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
0

LVL 45

Accepted Solution

sunnycoder earned 500 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

0

## Featured Post

Question has a verified solution.

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

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…
When there is a disconnect between the intentions of their creator and the recipient, when algorithms go awry, they can have disastrous consequences.
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201…
Do you want to know how to make a graph with Microsoft Access? First, create a query with the data for the chart. Then make a blank form and add a chart control. This video also shows how to change what data is displayed on the graph as well as form…
###### Suggested Courses
Course of the Month9 days, 21 hours left to enroll