snippetMinor
How to show that given language is unambiguous
Viewed 0 times
showlanguageunambiguousthathowgiven
Problem
Given following grammar:
$$
\begin{align}
S \rightarrow &A1B \\
A \rightarrow & 0A \mid \varepsilon \\
B \rightarrow & 0B \mid 1B \mid \varepsilon \\
\end{align}
$$
How can I show that this grammar is unambiguous? I need to find a grammar for the same language that is ambiguous, and demonstrate it.
I know if I was asked to prove that the language is ambigious then I should find two different parse trees for same string, but I don't know what to do.
$$
\begin{align}
S \rightarrow &A1B \\
A \rightarrow & 0A \mid \varepsilon \\
B \rightarrow & 0B \mid 1B \mid \varepsilon \\
\end{align}
$$
How can I show that this grammar is unambiguous? I need to find a grammar for the same language that is ambiguous, and demonstrate it.
I know if I was asked to prove that the language is ambigious then I should find two different parse trees for same string, but I don't know what to do.
Solution
To show a grammar is unambiguous you have to argue that for each string in the language there is only one derivation tree.
In this particular case you can observe that $A$ only generates $0$'s, so the $1$ generated by the start symbol $S$ must be the first $1$ in the string.
Any grammar can be made ambiguous by adding chain productions like $S\to S$.
In this particular case you can observe that $A$ only generates $0$'s, so the $1$ generated by the start symbol $S$ must be the first $1$ in the string.
Any grammar can be made ambiguous by adding chain productions like $S\to S$.
Context
StackExchange Computer Science Q#7518, answer score: 4
Revisions (0)
No revisions yet.