YES

We show the termination of the TRS R:

  f(a()) -> f(b())
  g(b()) -> g(a())

-- SCC decomposition.

Consider the dependency pair problem (P, R), where P consists of

p1: f#(a()) -> f#(b())
p2: g#(b()) -> g#(a())

and R consists of:

r1: f(a()) -> f(b())
r2: g(b()) -> g(a())

The estimated dependency graph contains the following SCCs:

  (no SCCs)