# Proof by induction method

Printable View

• March 14th 2010, 08:04 AM
Jagger
Proof by induction method
Hi!

Can someone explain me the way to do this exercise?

The exercise say's:

Consider the alphabet $\Sigma=\{a,b\}$ and the languages $\Gamma$ and $\Delta$ defined inductively with the following rules:

Proof that $\Gamma = \Delta$

$\Gamma$ is:

$(i) \epsilon\in\Gamma$

$(ii)\mbox{ If } \alpha\in\Gamma \Rightarrow \alpha a\in\Gamma$

$(iii)\mbox{ If }\alpha\in\Gamma \Rightarrow \alpha b\in\Gamma$

$\Delta$ is:

$(i)\epsilon\in\Delta$

$(ii)\mbox{ If }\alpha\in\Delta \Rightarrow a\alpha\in\Delta$

$(iii)\mbox{ If }\alpha\in\Delta \Rightarrow b\alpha\in\Delta$

Thank's
• March 14th 2010, 10:23 AM
emakarov
May I ask, what have you tried and where are you stuck?