有限状态自动机(FSA)重复输出问题：原因分析与修复求助

我正在构建一款有限状态自动机(FSA)，用于识别绵羊叫声字符串“baa...!”或奶牛叫声字符串“moo...!”，要求仅接受包含偶数个元音的输入。但当前实现的FSA存在异常：当输入字符串中的元音数量超过2个时，已接受的结果会出现重复输出。

实现代码 #

工具导入与FSA创建函数 #

import openfst_python

import sys
sys.path.append('/usr/local/lib/python2.7/site-packages/')
import pywrapfst as fst
from fststr import fststr

# 可视化FSA
import graphviz
from IPython.display import display

def create_fsa(alphabet, fsa_str):
    """Create and compile an FSA given an alphabet and string representation
    
    Params
    ------
    alphabet: `List[str]` 
        Input alphabet of the FSA
    fsa_str: str 
        String representation of the FSA 
        
    Returns the FSA object
    """
    st = fststr.symbols_table_from_alphabet(alphabet)
    compiler = fst.Compiler(isymbols=st, osymbols=st, keep_isymbols=True, keep_osymbols=True)
    compiler.write(fsa_str)
    fsa = compiler.compile()
    
    return fsa

FSA定义与测试代码 #

sheepcow_alphabet = ['a', 'b', 'm', 'o', '!']
sheepcow_fsa_str = """
0 1 b b 
1 2 a a
2 1 a a
2 3 a a
3 2 a a
1 4 ! !
4
0 5 m m
5 6 o o
6 5 o o
6 7 o o
7 6 o o
5 4 ! !
4
""" 


sheepcow_fsa = create_fsa(alphabet=sheepcow_alphabet, fsa_str=sheepcow_fsa_str)

# 可视化FSA
sheepcow_fsa.draw("FSAs/sheepcow_fsa.dot", portrait=True)
src = graphviz.Source.from_file("FSAs/sheepcow_fsa.dot")
display(src)

# 测试用例
accepted_strings = ['baa!', 'moo!', 'baaaa!', 'moooooo!']
rejected_strings = ['b', '!', 'oo!', 'baaa!', 'maa!', 'baaa!']

# 处理接受列表
for s in accepted_strings:
    print('SheepCow FSA processes string %s: %s' % (s, fststr.apply(s, sheepcow_fsa)))

# 处理拒绝列表
for s in rejected_strings:
    print('SheepCow FSA processes string %s: %s' % (s, fststr.apply(s, sheepcow_fsa)))

测试输出 #

SheepCow FSA processes string baa!: ['baa!']
SheepCow FSA processes string moo!: ['moo!']
SheepCow FSA processes string baaaa!: ['baaaa!', 'baaaa!']. # 重复输出
SheepCow FSA processes string moooooo!: ['moooooo!', 'moooooo!', 'moooooo!', 'moooooo!']. # 重复输出
SheepCow FSA processes string b: []
SheepCow FSA processes string !: []
SheepCow FSA processes string oo!: []
SheepCow FSA processes string baaa!: []
SheepCow FSA processes string maa!: []
SheepCow FSA processes string baaa!: []

当前FSA设计存在冗余的等价路径：

• 绵羊部分：同时设计了1↔2和2↔3两组循环来处理a的输入，这两组循环都能实现偶数个元音的计数，但它们是并行的独立路径。当输入4个a时，存在两条不同的路径可以到达接受状态，且输出完全相同，导致fststr.apply返回重复结果。
• 奶牛部分：同理，5↔6和6↔7两组循环造成了更多的路径组合，输入6个o时会产生4条等价路径，因此输出4次重复结果。

简化FSA结构，仅保留一套用于切换元音奇偶计数的状态循环，去掉冗余状态和边：

修复后的FSA定义 #

sheepcow_fsa_str_fixed = """
# 绵羊叫声路径：b + 偶数个a + !
0 1 b b 
1 2 a a
2 1 a a
1 4 ! !
# 奶牛叫声路径：m + 偶数个o + !
0 5 m m
5 6 o o
6 5 o o
5 4 ! !
# 接受状态
4
""" 

修复后的测试输出 #

替换原FSA定义为上述代码后，测试输出将变为：

SheepCow FSA processes string baa!: ['baa!']
SheepCow FSA processes string moo!: ['moo!']
SheepCow FSA processes string baaaa!: ['baaaa!']
SheepCow FSA processes string moooooo!: ['moooooo!']
SheepCow FSA processes string b: []
SheepCow FSA processes string !: []
SheepCow FSA processes string oo!: []
SheepCow FSA processes string baaa!: []
SheepCow FSA processes string maa!: []
SheepCow FSA processes string baaa!: []

修复后的FSA逻辑：

• 绵羊部分：状态1表示已输入b且元音数为偶数，状态2表示元音数为奇数；每输入一个a，在状态1和2之间切换，只有处于状态1（偶数元音）时输入!才能到达接受状态4。
• 奶牛部分：状态5表示已输入m且元音数为偶数，状态6表示元音数为奇数；每输入一个o，在状态5和6之间切换，只有处于状态5（偶数元音）时输入!才能到达接受状态4。

这样每个合法输入都只有唯一的路径到达接受状态，不会产生重复输出，同时满足仅接受偶数个元音的需求。

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