Dgdrxrt

Implication of namely

Processor speed limited at 0.4 Ghz

Ambiguity in the definition of entropy

How do conventional missiles fly?

GFCI outlets - can they be repaired? Are they really needed at the end of a circuit?

How to prevent "they're falling in love" trope

How to remove border from elements in the last row?

Theorists sure want true answers to this!

Is this draw by repetition?

Send out email when Apex Queueable fails and test it

What are the G forces leaving Earth orbit?

What do you call someone who asks many questions?

What is the fastest integer factorization to break RSA?

Can someone clarify Hamming's notion of important problems in relation to modern academia?

What is required to make GPS signals available indoors?

Did 'Cinema Songs' exist during Hiranyakshipu's time?

What is an equivalently powerful replacement spell for the Yuan-Ti's Suggestion spell?

Machine learning testing data

How to stretch the corners of this image so that it looks like a perfect rectangle?

Different meanings of こわい

Was the old ablative pronoun "med" or "mēd"?

What historical events would have to change in order to make 19th century "steampunk" technology possible?

Was the Stack Exchange "Happy April Fools" page fitting with the '90's code?

How can saying a song's name be a copyright violation?

Which string in this context free grammar shows that the CFG is ambiguous?

Context free grammar constructionContext free grammar to languageRight-Linear Context Free GrammarsAmbiguity of Context Free GrammarDescribe this language that is generated by Context Free GrammarContext free grammar of calculatorShow that this CFG is ambiguousContext-free grammarContext free grammar problemsbuild context free grammar

0

$begingroup$

I have the CFG with the production S:

S → SS ∣ ab ∣ a

I need to prove that this CFG is ambiguous. I'm having trouble finding a string suitable that will prove its ambiguity.

I've constructed parse trees with the leftmost derivations and can't find a way.

Of course I can't start with:

S -> ab
or
S -> a

So I need to start with

S -> SS

From there, I can get aab, aba, aa, abab

Or I can choose to use production S in either S which is what I feel I need to do.

So If I want to use the first S:

S -> SS -> SSa -> aaa

Using the second s,

S -> SS -> aSS -> aaa

Would this prove its ambiguity? Not sure if I solved my own problem just need confirmation

context-free-grammar

share|cite|improve this question

asked Mar 28 at 15:40

Ajeet KljhAjeet Kljh

75110

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Yes, it does prove ambiguity since there are two distinct parse trees for the same string.
  $endgroup$
  – Siddharth Bhat
  Mar 28 at 15:48
  

  
  
  
  

add a comment | 

0

$begingroup$

I have the CFG with the production S:

S → SS ∣ ab ∣ a

I need to prove that this CFG is ambiguous. I'm having trouble finding a string suitable that will prove its ambiguity.

I've constructed parse trees with the leftmost derivations and can't find a way.

Of course I can't start with:

S -> ab
or
S -> a

So I need to start with

S -> SS

From there, I can get aab, aba, aa, abab

Or I can choose to use production S in either S which is what I feel I need to do.

So If I want to use the first S:

S -> SS -> SSa -> aaa

Using the second s,

S -> SS -> aSS -> aaa

Would this prove its ambiguity? Not sure if I solved my own problem just need confirmation

context-free-grammar

share|cite|improve this question

asked Mar 28 at 15:40

Ajeet KljhAjeet Kljh

75110

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Yes, it does prove ambiguity since there are two distinct parse trees for the same string.
  $endgroup$
  – Siddharth Bhat
  Mar 28 at 15:48
  

  
  
  
  

add a comment | 

$begingroup$

I have the CFG with the production S:

S → SS ∣ ab ∣ a

I need to prove that this CFG is ambiguous. I'm having trouble finding a string suitable that will prove its ambiguity.

I've constructed parse trees with the leftmost derivations and can't find a way.

Of course I can't start with:

S -> ab
or
S -> a

So I need to start with

S -> SS

From there, I can get aab, aba, aa, abab

Or I can choose to use production S in either S which is what I feel I need to do.

So If I want to use the first S:

S -> SS -> SSa -> aaa

Using the second s,

S -> SS -> aSS -> aaa

Would this prove its ambiguity? Not sure if I solved my own problem just need confirmation

context-free-grammar

share|cite|improve this question

asked Mar 28 at 15:40

Ajeet KljhAjeet Kljh

75110

$endgroup$

share|cite|improve this question

asked Mar 28 at 15:40

Ajeet KljhAjeet Kljh

75110

share|cite|improve this question

asked Mar 28 at 15:40

Ajeet KljhAjeet Kljh

75110

asked Mar 28 at 15:40

Ajeet KljhAjeet Kljh

75110

asked Mar 28 at 15:40

Ajeet KljhAjeet Kljh

75110