正規表現で表現できる⇔オートマトンで受理できる
でしょ？
今回なら入力xに対し出力がtrickである場合を

[^t]*t[^r]*r[^ie]*i[^ce]*c[^ke]*k.*
|[^t]*t[^r]*r[^ie]*i[^ce]*c[^ke]*e[^ka]*k.*
...
(10パターン)
....

と正規表現だけで表現できてしまう