有限状态机程序

我的任务是创建一个小程序,它可以从输入中读取FSM的定义,从输入中读取一些字符串,并根据定义确定FSM是否接受这些字符串.我需要用C,C++或Java来编写它.我已经在网上搜索了如何开始的想法,但我能找到的最好的是维基百科关于基于Automata的编程的文章.提供的C示例似乎使用枚举列表来定义状态,如果状态是事先进行硬编码则没问题.同样,我需要能够实际读取状态的数量和每个状态应该做的定义.任何建议表示赞赏.

更新:我可以使字母变小(例如{ab})并采用其他约定,例如开始状态始终为状态0.我可以对状态数施加合理的限制,例如不超过10.

问题摘要:

我如何实施FSA？

Mike Dunlave.. 7

首先,获取所有状态(N个)的列表,以及所有符号(M个)的列表.然后有两种方法,解释或代码生成:

解释.创建一个NxM矩阵,其中矩阵的每个元素都填入相应的目标状态编号,如果没有则填充-1.然后只需要一个初始状态变量并开始处理输入.如果你达到-1状态,你就失败了.如果输入符号用完而没有进入成功状态,则会失败.否则你就成功了.

代码生成.用C或您最喜欢的编译器语言打印出一个程序.它应该有一个初始化为start状态的整数状态变量.它应该在输入字符上有一个for循环,包含状态变量的开关.每个状态应该有一个案例,并且在每种情况下,在当前字符上都有一个switch语句,用于更改状态变量.

如果你想要比2更快的东西,这肯定会让你不及格(!),摆脱状态变量,而是使用goto :-)如果你不知所措,你可以安慰自己知道这是编译器做的.

PS你可以得到你的˚F变为一个,如果你认识到循环等.在状态图并打印出相应的,而与是否语句,而不是使用goto语句.

首先,获取所有状态(N个)的列表,以及所有符号(M个)的列表.然后有两种方法,解释或代码生成:

解释.创建一个NxM矩阵,其中矩阵的每个元素都填入相应的目标状态编号,如果没有则填充-1.然后只需要一个初始状态变量并开始处理输入.如果你达到-1状态,你就失败了.如果输入符号用完而没有进入成功状态,则会失败.否则你就成功了.

代码生成.用C或您最喜欢的编译器语言打印出一个程序.它应该有一个初始化为start状态的整数状态变量.它应该在输入字符上有一个for循环,包含状态变量的开关.每个状态应该有一个案例,并且在每种情况下,在当前字符上都有一个switch语句,用于更改状态变量.

如果你想要比2更快的东西,这肯定会让你不及格(!),摆脱状态变量,而是使用goto :-)如果你不知所措,你可以安慰自己知道这是编译器做的.

PS你可以得到你的˚F变为一个,如果你认识到循环等.在状态图并打印出相应的,而与是否语句,而不是使用goto语句.