I have an encoding of an unambiguous grammar $G$. Can I apply a morphism $σ$ so that the grammar becomes ambiguous?

I have no clear concepts about this, only the idea: "grammar $G$ is ambiguous if there's a string $x \in L(G)$ having two different leftmost derivations in $G$". I would like a good explanation and if it's possible, an example.


I will consider two alphabets, $Σ_1$ and $Σ_2$, where $\Sigma_1$ is the terminal alphabet of $G$. A morphism is a function of the form $h\colon Σ_1^* \to Σ_2^*$ which satisfies: $h(xy)=h(x)h(y)$ for all $x,y \in \Sigma_1^*$. When applying the morphism to a grammar on $\Sigma_1$, the result is a grammar on $\Sigma_2$ (that is, the morphism is only applied to the terminals in $G$).

  • 1
    $\begingroup$ I still don't understand where the morphism comes in. Can you define what a morphism is, and how do you "multiply" (presumably, apply) a morphism to a grammar? $\endgroup$ Mar 15 '17 at 14:16
  • $\begingroup$ i edited the question. Σ1 -> Σ2 | σ(uv) = σ(u) σ(v) ; I have G = <V,Σ1,a,S> | L (G) = L, then σ(G) = <V, Σ2, {X -> σ(u) | {X -> u } € a},S> then L(σ(G)) = σ(L(G)) = σ(L), this is the form that i have to apply the morphism without make any change to the variables. $\endgroup$ Mar 15 '17 at 15:22
  • $\begingroup$ You haven't defined in the question what it means to apply a morphism to a grammar, or what the resulting grammar is. It's well-defined what it means to apply $\sigma$ to a language (e.g., $L(G)$), but it's not clear to me what you mean by applying $\sigma$ to a grammar (e.g., $G$). Can you edit the question to provide a self-contained definition of what you mean by that? We want questions to contain everything needed to understand what you are asking (people shouldn't have to read the comments to understand your question). Thank you! $\endgroup$
    – D.W.
    Mar 15 '17 at 16:49

The answer depends on the grammar $G$. If $G$ generates at most one word, then no morphism will make it ambiguous (prove!). If $G$ generates more than one word, then the morphism sending all characters to the empty string will make it ambiguous (why?).


Your Answer

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

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