====== TD2 : Syntaxe vs. Sémantique ======

===== Le langage "nat" des suites binaires =====

  * sémantique : entiers naturels
  * syntaxe : représentation unaire

^ Grammaire arithmétique ^
| C -> 0 %%|%% 1 %%|%% ... %%|%% 9 |
| N -> C<sup>+</sup>  |
| E -> N %%|%% E+E %%|%% E-E %%|%% E*E |
| V -> a %%|%% b %%|%% ... %%|%% z |

==== Donner sa sémantique dénotationnelle ====

  * <jsm>\left[\!| 0 |\!\right]_{bin} = 0_{\mathbb{N}} </jsm> et <jsm>\left[\!| 1 |\!\right]_{bin} = 1_{\mathbb{N}} </jsm>
  * <jsm>\left[\!| 0 |\!\right]_{nat} = \left[\!| 0 |\!\right]_{bin} = 0_{\mathbb{N}} </jsm>
  * <jsm>\left[\!| 1 |\!\right]_{nat} = \left[\!| 1 |\!\right]_{bin} = 1_{\mathbb{N}} </jsm>
  *  <jsm>\left[\!| n 0 |\!\right]_{nat} = 2 \times \left[\!| n |\!\right]_{nat}+\left[\!| 0 |\!\right]_{bin} = 2 \times \left[\!| n |\!\right]_{nat} </jsm>
  *  <jsm>\left[\!| n 1 |\!\right]_{nat} = 2 \times \left[\!| n |\!\right]_{nat}+\left[\!| 1 |\!\right]_{bin} = 2 \times \left[\!| n |\!\right]_{nat} + 1 </jsm>
avec '+' et 'x' les opérations habituelles de <jsm>\mathbb{N}</jsm>

Montrons que FIXME à completer