1. Les deux productions EE + E et EE * E ne sont pas en forme normale de Chomsky car, d'une part leur membre droit contient trois symboles et d'autre part l'un de ces symboles est un terminal. La production SE n'est pas non plus en forme de Chomsky.

  2. On procède donc en trois étapes.
    1. Il suffit de remplacer les terminaux par des non terminaux et d'ajouter les productions correspondantes.
      SE          Ei          EE P E          P+          EE M E          M*
    2. Ici encore c'est assez facile : remplacer une règle ABCD par deux règles ABE et ECD.
      SE          Ei
      EE Ep         EpP E          P+
      EE Em          EmM E          M*
    3. C'est à peine plus dur, il faut remplacer la production SE par les productions S → α où les α sont les membres droits des productions E → α.
      Si          SE Ep          SE Em
      Ei
      EE Ep         EpP E          P+
      EE Em          EmM E          M*
  3. Code de isCNF, qui abuse des return, mais c'est tellement pratique.
    static boolean isTerm(char c) { return !(isNonTerm(c) || Character.isSpaceChar(c)) ; } static boolean isNonTerm(char c) { return Character.isUpperCase(c) ; } static boolean isCNF(Rules rs) { for ( ; rs != null ; rs = rs.next) { List rhs = rs.rhs ; if (rhs == null) return false ; // Production vide if (rhs.next == null) { if (!isTerm(rhs.val)) return false ; // Production AB } else { if (rhs.next.next == null) { if (!(isNonTerm(rhs.val) && isNonTerm(rhs.next.val))) return false ; // Membre droit de taille 2, distinct de AB } else { return false ; // Membre droit de taille > 2 } } } return true ; }