将NFA存储到数据结构中
我获得了 NFA，并且需要使用数据结构（我不能使用递归下降解析器）来存储它。一旦 NFA 存储在数据结构中，我就会得到一个字符串，根据给定的 NFA 检查该字符串是否有效。
有人可以建议一个用于存储 NFA 的数据结构吗？另外，如果有任何开源 C 语言示例也会有很大帮助。
I am provided with a NFA and I need to use a data structure (I can not use recursive descent parser) for storing it. Once the NFA is stored in a data structure I am given a string to check if the string is valid according to the NFA given or not.
Can someone please suggest a data structure for storing a NFA? Also if there are any opensource c language examples that would help a lot.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
NFA 只是一组三元组
State x Input ->状态。用从 0（或其他定义的起点）开始的连续范围内的小整数表示状态通常很方便。输入符号也可以直接映射到小整数（如果所有转换都是 ascii 字符，则为 ascii 代码）或通过在读取机器时保留清单来映射。制作三元组列表效率极低，制作哈希表则太过分了；一个合理的中间值是一个二维数组。请记住，机器是不确定的，因此给定的[状态，输入符号]对可能映射到集合下一个状态。您可以使用子集构造将 NFA 确定为 DFA。这简化了数据结构，但其大小也可能呈指数级增长。
An NFA is just a set of triples
State x Input -> State. It's usually convenient to represent a State with a small integer in a consecutive range starting at 0 (or some other defined starting point). Input symbols can also be mapped onto small integers, either directly (ascii code if all the transitions are ascii characters) or by keeping an inventory while you read the machine. Making a list of triples is highly inefficient and making a hash table is overkill; a plausible intermediate is a two-dimensional array. Remember that the machine is Nondeterministic, so a given [state, input symbol] pair might map to a set of next states.You can determinize the NFA into a DFA using the Subset Construction. That simplifies the data structure but it can also blow up exponentially in size.