1. Les deux productions E → E + E et E → E * 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 S → E 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.
      S → E          E → i          E → E P E          P → +          E → E M E          M → *
    2. Ici encore c'est assez facile : remplacer une règle A → BCD par deux règles A → BE et E → CD.
      S → E          E → i
      E → E Ep         Ep → P E          P → +
      E → E Em          Em → M E          M → *
    3. C'est à peine plus dur, il faut remplacer la production S → E par les productions S → α où les α sont les membres droits des productions E → α.
      S → i          S → E Ep          S → E Em
      E → i
      E → E Ep         Ep → P E          P → +
      E → E Em          Em → M 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 A → B } 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 ; }