python - Python 中 {ab, abc}* 的非确定性有限自动机
问题描述
我一直在尝试绘制这个非确定性有限自动机:
语言 {ab, abc}* 的状态数不超过 3 的 NFA,我得到了下图中的解决方案:
问题似乎是代码逻辑,因为我的代码总是打印“拒绝。如果有人可以就如何编写此算法提供一些提示,我将不胜感激。
print("Insert below the string: ")
string = str(input())
def state_q0(string):
if len(string) == 0:
print("string not accepted")
else:
if string[0] == "a":
state_q1(string[1:])
elif string[0] == "b":
print("rejected")
def state_q1(string):
if len(string) == 0:
print("string not accepted")
else:
if string[1] == "b":
state_q2(string[2:])
else:
print("rejected")
def state_q2(string):
if len(string) == 0:
print("string not accepted")
else:
if string[2] == "c":
print("accepted -> q0")
elif string[2] == "b":
print("rejected")
state_q0(string)
解决方案
您应该始终查看字符串的第一个字符,并使用除第一个字符之外的所有内容调用递归调用。
您的图表中也没有注明,但我认为这q0
是接受状态,因为它对应于(ab + abc)*
.
所以按照你的风格(我个人不会使用,但没关系):
def q0(s):
if not s: return "accept" # Accepting state.
if s[0] == "a": return q1(s[1:])
return "reject"
def q1(s):
if not s: return "reject"
# NFA, must try both edges.
if (s[0] == "b" and q0(s[1:]) == "accept" or
s[0] == "b" and q2(s[1:]) == "accept"):
return "accept"
return "reject"
def q2(s):
if not s: return "reject"
if s[0] == "c": return q0(s[1:])
return "reject"
然而,我将如何编码 NFA 是这样的:
transitions = [
{"a": {1}},
{"b": {0, 2}},
{"c": {0}}
]
starting_state = 0
accepting_states = {0}
def nfa(w):
cur_states = {starting_state}
for c in w:
if not cur_states: return "reject"
cur_states = set.union(*
(transitions[s].get(c, set()) for s in cur_states))
return "accept" if cur_states & accepting_states else "reject"
推荐阅读
- oracle - 如何使用动态字段名提取值 trom 行类型?
- events - 事件驱动的微服务 - 如何初始化旧数据?
- javascript - 默认选中的单选按钮保持为真
- bigcommerce - 您如何在 Bigcommerce 的自定义主题设置中输入/存储 URL?
- unity3d - IOS中Cocos2d-x UserDefault数据的路径/位置?
- javascript - 有没有办法找出试图访问对象的哪个键?
- python - Pandas Grouper - 指定没有数据的结束日期
- android - 基于 Android 状态的形状叠加(现代方法)
- azure - Azure Active Directory B2C 电话注册问题
- sql-server - 从现有架构创建架构?