Grammar derivation

159 Views Asked by At

Given these grammar productions:

$$\begin{align*} &S\to A1B\\ &A\to 0A\mid\lambda\\ &B\to 0B\mid 1B\mid\lambda \end{align*}$$

And given string $w = 01101$

If I wanted to make a) leftmost derivation and b) rightmost derivation, I thought it would work like this:

a) $S \rightarrow A1B \rightarrow 01B \rightarrow 011B \rightarrow 0110B \rightarrow 01101$

b) $S \rightarrow A1B \rightarrow A11B \rightarrow A110B \rightarrow A1101 \rightarrow 01101$

I'm learning about left/right derivations and not sure if they properly applied here. Maybe someone can tell me where I'm misunderstanding this concept.

EDIT:

Thanks for the great answer, if I'm understanding correctly then I should be doing it like this:

a) $S \rightarrow A1B \to 0A1B \rightarrow 01B \rightarrow 011B \rightarrow 0110B \to 01101B \rightarrow 01101$

b) $S \rightarrow A1B \rightarrow A11B \rightarrow A110B \to A1101B \rightarrow A1101 \to 0A1101 \rightarrow 01101$

1

There are 1 best solutions below

6
On BEST ANSWER

In (a) the step $A1B\Rightarrow 01B$ is impossible, because there is no production $A\to 0$. Two steps are required: $A1B\Rightarrow 0A1B\Rightarrow 01B$. The step $0110B\Rightarrow 01101$ is also impossible; again you need two steps, $0110B\Rightarrow 01101B\Rightarrow 01101$.

In (b) you have the same problem with $A110B\Rightarrow A1101$ and $A1101\Rightarrow 01101$: the first should be $A110B\Rightarrow A1101B\Rightarrow A1101$, and the second $A1101\Rightarrow 0A1101\Rightarrow 01101$.