#nfa simulation for (a|b)*abb
#state 4 is a trap state
import sys
def main():
transition = [[[0,1],[0]], [[4],[2]], [[4],[3]], [[4],[4]]]
input = raw_input("enter the string: ")
input = list(input) #copy the input in list because python strings are immutable and thus can't be changed directly
for index in range(len(input)): #parse the string of a,b in 0,1 for simplicity
if input[index]=='a':
input[index]='0'
else:
input[index]='1'
final = "3" #set of final states = {3}
start = 0
i=0 #counter to remember the number of symbols read
trans(transition, input, final, start, i)
print "rejected"
def trans(transition, input, final, state, i):
for j in range (len(input)):
for each in transition[state][int(input[j])]: #check for each possibility
if each < 4: #move further only if you are at non-hypothetical state
state = each
if j == len(input)-1 and (str(state) in final): #last symbol is read and current state lies in the set of final states
print "accepted"
sys.exit()
trans(transition, input[i+1:], final, state, i) #input string for next transition is input[i+1:]
i = i+1 #increment the counter
main()
样本输出:(接受以abb结尾的字符串)
enter the string: abb
accepted
enter the string: aaaabbbb
rejected
在这里,我给出了NFA的递归解决方案。
考虑以下nfa:
可以使用列表列表来表示转换,如下所示:
转换=
[[[0,1],[0]], [[4],[2]], [[4],[3]], [[4],[4]],[[4],[4]]]
注意:状态4是一个假设状态。一旦你去了那个州,你就不能再往前走了。当您无法从当前状态读取输入时,它会很有帮助。直接进入状态4,并说当前进度不接受输入(通过返回检查其他可能性)。e、 g,如果您在
q1
,并且当前的输入符号是'a'
,则转到状态4并进一步停止计算。下面是Python代码:
样本输出:(接受以abb结尾的字符串)
。。。。。。
这是我的dfa实现版本,如果您正在寻找一个更面向对象的实现。然而,约翰·科尔曼的回答给了我一点启发。
表示DFA的一种简单方法是使用字典。为每个州创建一个由字母表的字母键控的字典,然后创建一个由州键控的全局字典。例如,来自Wikipedia article on DFAs的以下DFA
可以用这样的字典来表示:
对从所讨论的字母表中提取的输入字符串“运行”dfa(在指定初始状态和接受值集之后)很简单:
您从初始状态开始,一个字符一个字符地遍历字符串,在每个步骤中只需查找下一个状态。单步执行完字符串后,只需检查最终状态是否在接受状态集中。
例如
对于NFAs,您可以在转换字典中存储可能的状态集,而不是单个状态,并使用
random
模块从可能的状态集中选择下一个状态。相关问题 更多 >
编程相关推荐