Launguages in Discrete Mathematical Structures II

121 Views Asked by At

For the grammar $G$ specified, draw a derivation tree for each of the given strings or conclude that the string is not derivable from $v_0$.

$G = (V, S, v_0 , \rightarrow ), \\ V = \{v_o, v_1, x, y, z\}, \\ S = \{x, y, z\}$

$v_0 \rightarrow xv_0 \\ v_0 \rightarrow yv_1 \\ v_1 \rightarrow yv_1 \\ v_1 \rightarrow z$

  1. The string $x^2y^2z$
  2. The string $xy^2$
1

There are 1 best solutions below

0
On

Note that in order to get rid of the initial symbol $v_0$, you must at some point apply the production $v_0\to yv_1$, at which point you have the non-terminal symbol $v_1$ in your string. In order to get rid of $v_1$, you must at some point apply $v_1\to z$. Thus, every derivable terminal string contains the symbol $z$, and it follows that $xy^2$ is not derivable.

In fact it’s not hard to see exactly which strings are derivable. To begin a derivation we can apply $v_0\to xv_0$ any number $n\ge 0$ of times, but eventually we must apply $v_0\to yv_1$ in order to get rid of $v_0$; at that point we have $x^nyv_1$. We can now apply $v_1\to yv_1$ any number $m\ge 0$ of times, but eventually we must apply $v_1\to z$. At that point we’re done, and we have $x^nyy^mz$, or simply $x^ny^{m+1}z$, where $m$ and $n$ are any non-negative integers. Clearly $x^2y^2z$ is in this language, with $n=2$ and $m=1$. That should tell you exactly how to derive $x^2y^2z$, and once you have the derivation, converting it to tree form is straightforward. The first step of the derivation is evidently $v_0\Rightarrow xv_0$, so your derivation tree will begin like this:

$$\begin{array}{ccc} &&v_0\\ &\diagup&&\diagdown\\ x&&&&v_0 \end{array}$$