-1
$\begingroup$

I don't know if it is the right site to ask this. But we're studying about ambiguities of grammar. Including left most derivation and right most derivation. We are given the problem:

E -> E * E | E + E | N
N -> 0N | 1N |
Output: 0110 + 110 * 01111

My question is, is there a shortest way to attain that output? Because in my leftmost and rightmost derivation it took 7 lines.

$\endgroup$

closed as unclear what you're asking by D.W., David Richerby, Luke Mathieson, Juho, Rick Decker Jan 19 '15 at 13:49

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ What do you mean by "Is there a shortest way?" The length of any derivation is a natural number and any set of natural numbers has a unique smallest element. So the answer to the literal question is "Yes, there is a shortest way." What are you actually looking for? $\endgroup$ – David Richerby Jan 18 '15 at 13:20
  • $\begingroup$ Did you mean to ask: "What is the best known time complexity for determining whether a Grammar is ambiguous?" $\endgroup$ – Francesco Gramano Jan 18 '15 at 18:34
  • $\begingroup$ Your grammar won't generate any strings of terminals unless you add some productions like $N\rightarrow 0\mid 1$. $\endgroup$ – Rick Decker Jan 18 '15 at 19:06
1
$\begingroup$

As you said, the grammar is ambiguous.

There are two ways of producing the result $0110 + 110 \ast 01111$:
The one for $(0110 + 110) \ast 01111$ and the other for $(0110 + 110) \ast 01111$.
Try them both.


As for your question,

Is there a shortest way to attain that output? Because in my leftmost and rightmost derivation it took 7 lines.

"Number of Lines" sounds quite vague.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.