如何在Prolog中为土耳其语形态分析终态自动机实现DFS？

我有一个用于土耳其语形态分析的终态自动机，土耳其语是黏着语，目标是拆分单词并找出对应的语素变体和语素。以下是分析示例：

分析查询示例 #

?- analyze('kediler', Allomorphs, Morphemes).
Allomorphs = [kedi, ler],
Morphemes  = [noun, plur] 

终态自动机代码片段 #

final(qv4b).
final(qv4c).
final(qv5).
final(qv5a).

% 初始转移规则
t(q0,noun,qn1).
t(q0,verb,qv1).

目前我的分析结果存在错误，需要逐词、逐语素测试，因此希望实现深度优先搜索（DFS）算法查看所有可能的分析结果，具体实现路径如下：

• 定义核心递归逻辑
  从自动机初始状态q0出发，维护四个跟踪变量：当前自动机状态、剩余待匹配的单词片段、已收集的语素变体列表、已收集的语素列表。递归终止条件为：剩余单词片段为空，且当前状态是final/1定义的终态，此时将当前的变体和语素组合记录为一组有效结果。

• 遍历状态转移规则
  对每个当前状态CurrentState，查询所有t(CurrentState, Morpheme, NextState)转移规则。针对每个转移规则，匹配对应语素的所有可能变体：

  • 提前为每个语素（如noun、plur）定义所有可能的语素变体（如noun对应各类名词词干，plur对应ler、lar等）
  • 检查剩余单词是否以某个变体开头，若匹配成功，截取剩余单词（移除匹配的前缀），将该变体和语素加入对应列表，递归进入NextState继续处理。

• 处理黏着语形态变化特例
  土耳其语存在元音和谐、辅音同化等形态变化，匹配语素变体时需加入这些规则判断：

  • 元音和谐：确保后缀元音与词干元音匹配（如词干含e类元音时用ler，含a类元音时用lar）
  • 辅音同化：处理词干末尾辅音对后缀的影响，比如浊辅音后的后缀变体调整，需在匹配逻辑中加入这些规则。

• 收集所有有效结果
  递归过程中，每满足终止条件就将当前的Allomorphs和Morphemes加入结果集合，最终返回所有可能的分析结果，方便对比排查错误。

• 测试与调试
  针对单个单词（如kediler）调用DFS分析函数，输出所有拆分结果，对比预期结果定位问题：

  • 检查是否遗漏了语素变体的转移规则
  • 验证final/1定义的终态是否正确，避免合法结果被过滤或非法结果被误判。

内容的提问来源于stack exchange，提问作者MehmetG