Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 1014
  • Last Modified:

Is the following solution for pairwise disjointment correct?

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
missymadi
Asked:
missymadi
  • 3
  • 2
1 Solution
 
sunnycoderCommented:
> 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
 
missymadiAuthor Commented:
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
 
sunnycoderCommented:
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
 
missymadiAuthor Commented:
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
 
sunnycoderCommented:
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

Get your problem seen by more experts

Be seen. Boost your question’s priority for more expert views and faster solutions

  • 3
  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now