Cojamos el siguiente autómata finito (este es no determinista pues hay dos transiciones y desde el estado A) para el alfabeto S = { x, y }:

• Los no terminales definen el conjunto de estados S de M. En nuestro caso se trata de las etiquetas que le hemos puesto a los estados: S, A, B, C.
• El símbolo inicial es i. En nuestro caso es el estado que hemos etiquetado como S.
• Las reglas de reescritura son de la forma P ® xQ si la tripleta (P, x, Q) está en r (si existe la transición del estado P al Q con la etiqueta x):
   
  + Transición del estado S al A con etiqueta x: S ®xA
  + Transición del estado S al B con etiqueta y: S ®yB
  + Transición del estado A al A con etiqueta y: A ®yA
  + Transición del estado A al C con etiqueta y: A ®yC
  + Transición del estado B al C con etiqueta x: B ®xC
  + Transición del estado B al B con etiqueta y: B ®yB
• Q ® l si Q está en F. En nuestro caso, los estados A, B y C son de aceptación por lo tanto también tendremos las reglas:
  
  + A ® l
  + B ® l
  + C ® l