0
$\begingroup$

S-> AAB|ABA|BAA|epsilon

A->aS

B->bS

this is a grammar of the language L4 = {w ∈ Σ*: #a(w) = 2#b(w)} over Σ = {a, b}

Does the following examples shows that the L4 is ambiguous?

S->AAB->aSAB->aAB->aaSbS->aab

S->AAB->aSaSbS->aab

I'm not sure if these derivations are the same, if they are not, what are the derivations that shows the ambiguity of L4?

$\endgroup$
  • 2
    $\begingroup$ Welcome to CS StackExchange! What are the pound signs (#) in your equation? $\endgroup$ – Ben I. May 17 '17 at 18:22
  • 2
    $\begingroup$ Have you tried applying the definition of ambiguous? Where did you get stuck? Have you tried searching this site? There are lots of questions here that explain the notion of ambiguity in grammars; you should study them, then try to solve your question again. $\endgroup$ – D.W. May 17 '17 at 18:34
  • $\begingroup$ From this Wiki's article https://en.wikipedia.org/wiki/Ambiguous_grammar we have: an ambiguous grammar is a context-free grammar for which there exists a string that can have more than one leftmost derivation or parse tree. Are yours leftmost derivations? If yours are leftmost derivations and are different, then, yes, your grammar is ambiguous. $\endgroup$ – nbro May 17 '17 at 22:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.