Showing that calculus are (not) equivalent

29 Views Asked by At

Let $\mathcal{A} = \{ x,y \}$ be an alphabet. Consider the following rules for derivation:

$R_1 : \begin{array}{c} \hline \epsilon \end{array},\\R_2: \begin{array}{c} z \\\hline zx \end{array},~ R_3: \begin{array}{c} z \\\hline xz \end{array}, \\R_4: \begin{array}{c} z \\ z' \\\hline zyz'y \end{array},~ R_5: \begin{array}{c} z \\ z' \\\hline yzyz' \end{array}, \\R_6: \begin{array}{c} z \\\hline yyzyy \end{array}$,

where $\epsilon$ is the empty word.

I want to show that for $\mathcal K_4 := \{ R_1,R_2,R_3,R_4 \}, ~ \mathcal K_5 := \{ R_1,R_2,R_3,R_5 \}, ~ \mathcal K_6 := \{R_1, R_2,R_3,R_6 \}$

  1. $\mathcal K_4 \equiv \mathcal K_5$
  2. $\mathcal K_4 \not\equiv \mathcal K_6 \not\equiv \mathcal K_5$

Part 1 seems obvious because of $R_2$ and $R_3$, but I don't really know how to use the rules to prove that. And what is for 2.?

1

There are 1 best solutions below

0
On BEST ANSWER

Has your text or notes introduced the concept of a derived rule? If so, a natural approach to part 1 would be to show that $R_5$ is a valid derived rule in $\mathcal K_4$ and $R_4$ is a valid derived rule in $K_5$. This will allow you to translate any derivation in $\mathcal K_4$ to one in $\mathcal K_5$ and vice versa.

For part 2, you can prove by induction that in every word that $\mathcal K_6$ can derive, the number of $\mathtt y$s is a multiple of $4$. However, $\mathcal K_4$ (and $\mathcal K_5$) derives $\mathtt{yy}$.