有人可以比我更简洁地向SO社区描述NFA到DFA的转换算法吗？(最好是500字以内.)我见过的图表和讲座只会让我以为我曾经认识的东西感到困惑.我最有信心从状态图生成初始NFA转换表,但之后,我丢失了epsilons和子集中的DFA.
1)在转换(delta)表中,哪一列代表新的DFA状态？它是生成状态的第一列吗？
2)在下面我的例子的第{2,3}行中,{2,3}在状态图方面对NFA的意义是什么？(对不起,我必须在图片中思考.)我认为这将是DFA中的"输入0回环"？
3)从表格到DFA或识别所得到的DFA的接受状态的任何简单的"经验法则"？
有限自治
delta | 0 | 1 |
=======+=======+========+
{1} |{1} |{2} |
{2} |{3} |{2,3} |
{3} |{2} |{2,4} |
{2,3} |{2,3} |{2,3,4} |
{2,4} |{3,4} |{2,3,4} |
{2,3,4}|{2,3,4}|{2,3,4} |
{3,4} |{2,4} |{2,4} |
编辑:这是上面的点格式表,欢呼Regexident.
digraph dfa {
rankdir = LR;
size = "8,5"
/* node [shape = doublecircle]; "1";*/
node [shape = circle];
"1" -> "1" [ label = "0" ];
"1" -> "2" [ label = "1" ];
"2" -> "3" [ …我正在为自动机理论做一个任务,我必须通过确定性有限自动机的转换函数来确定一个单词是否被接受
我有这个输入文件:
6 8 0 2
2
5
0 0 a
0 1 a
1 1 b
1 2 c
1 3 c
3 4 d
4 4 d
4 5 d
3
aaabcccc
aabbbbcdc
acdddddd
输入以4个整数开始,第一个是自动机的状态数,第二个是自动机的转换数,第三个数是初始状态,然后是最终状态数.然后是最终状态(在示例中,最终状态是2和5).
然后是N行(N是转换的数量),每个都有2个整数和一个字符I,J和C,表示转换的状态,即转换从状态i转到状态J,字符为C.在这一行之后加上一个整数S,它将包含要测试的字符串数,然后是包含相应字符串的S行.
该程序的输出应为:
Case #2:
aaabcccc Rejected
aabbbbcdc Rejected
acdddddd Accepted
它应该说是否接受或拒绝字符串.到目前为止,我只使用输入编写了工作.
我不知道如何最方便地表示自动机.我应该只使用数组吗？我将什么逻辑应用于数组？有没有办法在不事先知道自动机字母表的情况下做到这一点？我需要一个数据结构来表示自动机吗？我对这项任务感到有点困惑,并希望有一些想法,一些伪代码或想法.代码是用另一种语言编写的吗？我不想要解决方案,因为我想做我的任务但是如果我可以使用一些帮助
我目前正在研发扫描仪发生器.发电机已经正常工作.但是当使用字符类时,算法变得非常慢.
扫描仪生成器为UTF8编码文件生成扫描仪.应支持全范围的字符(0x000000到0x10ffff).
如果我使用大字符集,就像任何运算符'.' 或者unicode属性{L},nfa(以及dfa)包含很多状态(> 10000).因此,将nfa转换为dfa并创建最小dfa需要很长时间(即使输出最小dfa只包含几个状态).
这是我当前创建nfa的字符集部分的实现.
void CreateNfaPart(int startStateIndex, int endStateIndex, Set<int> characters)
{
transitions[startStateIndex] = CreateEmptyTransitionsArray();
foreach (int character in characters) {
// get the utf8 encoded bytes for the character
byte[] encoded = EncodingHelper.EncodeCharacter(character);
int tStartStateIndex = startStateIndex;
for (int i = 0; i < encoded.Length - 1; i++) {
int tEndStateIndex = transitions[tStartStateIndex][encoded[i]];
if (tEndStateIndex == -1) {
tEndStateIndex = CreateState();
transitions[tEndStateIndex] = CreateEmptyTransitionsArray();
}
transitions[tStartStateIndex][encoded[i]] = tEndStateIndex;
tStartStateIndex = tEndStateIndex;
}
transitions[tStartStateIndex][encoded[encoded.Length - 1]] = endStateIndex; …我现在正在阅读编译器和解析器架构,我想知道一件事......当你有XML,XHTML,HTML或任何基于SGML的语言时,词法分析器的作用是什么以及令牌是什么？
我读过,令牌就像为词法分析器准备的单词一样.虽然我没有找到用于语言行C,C++,Pascal等的令牌的问题,其中有关键字,名称,文字和其他由空格分隔的类似字符串的字符串,但是我有一个问题,因为它没有'任何话!它只是与标记(标签)交错的纯文本.
我心里想,可能是这些标签和纯文本片段都是令牌,类似的东西:[TXT][TAG][TAG][TXT][TAG][TXT][TAG][TAG][TXT]....这将是比较合理的,因为SGML并不关心有什么标记分隔符中<和>(当然,它识别特殊处理的说明和定义时,它创立?或!为下一个字符,评论属于该组太),和SGML标记生成器能是XML/HTML/XHTML解析器的基础.
但后来我意识到<标记内部可能会有一些字符作为其他语法的一部分:属性值: - /即使将<字符放在属性值中也不是很好(最好用<它),许多浏览器和编辑处理这些并将它们<视为属性值的一部分,而不是标记分隔符.
它使事情变得复杂,因为我没有看到通过词法分析器中的简单确定性有限自动机(DFA)识别标记的方法.看起来它需要一个单独的自动机上下文,当它在标签内时,另一个上下文遇到一个属性值时.这需要一堆状态/上下文我认为,所以DFA可能无法处理.我对吗？
你有什么看法？从标签(标记)和纯文本制作令牌是否合适？
在这里:http://www.antlr.org/wiki/display/ANTLR3/Parsing+XML
使用某种不同的技术:他们对待<和>(和</和/>)作为分隔标记,标签内,他们使用GENERIC_ID的令牌等他们通常将大部分工作转移到解析器上.但是他们还必须改变标记化器的上下文:它们在纯文本中使用不同的上下文,并且在标记中使用不同(但是他们忘记了属性值上下文我认为,因为第一次出现>将在标签中结束标记).
那么解析类似SGML的语言的最佳方法是什么？那个词法分析器真的用在那里吗？如果是,那么代币是什么字符串？
有谁知道在C#中有任何好的NFA和DFA实现,可能实现两者之间的转换？我希望能够构建一个NFA,然后将其自动转换为DFA,但无需编写我自己的代码,这将花费很长时间.有这个 Python代码,也许我可以使用并使用IronPython与C#集成,但Python很慢.
我有一个远程"代理",当递给一个字符串时返回"是"或"否".与这个代理进行通信是很昂贵的,所以我希望找到一个库,它允许我在给出正面和负面反馈的情况下迭代地构建正则表达式,同时对其构造有所了解.这将允许我在发送方缓存答案.
例如,假设我们用"good"查询代理并收到"yes".初始派生的正则表达式应该是"好的".
假设我用"goop"查询然后收到"是".我希望派生的正则表达式是"goo [dp]",而不是"good | goop".
等等.
我在派生的正则表达式中不需要回溯或任何其他花哨的非线性时间操作.据推测,生成的正则表达式将成为引擎盖下的DFA.有谁知道任何能够做到这一点的c/c ++正则表达式库？或者,为什么这是一个愚蠢的想法和更好的解决我的真正问题的原因也将是有用的.
找不到任何肯定的东西.任何epsilon过渡的NFA都是epsilon-NFA？谢谢.
(我刚刚学习如何编写编译器,所以如果我做出任何不正确的声明,请纠正我)
当人们可以简单地使用正则表达式时,为什么还有人会在代码(goto语句,表驱动的实现)中实现DFA？据我所知,词法分析器接收一串字符并生成一个令牌列表,这些令牌在语言的语法定义中是终端,使得它们可以用正则表达式来描述.绕过一堆正则表达式会不会更容易,如果找到匹配就会突破循环？
有没有人知道包含典型编译器课程的在线课程/大学讲座？我有计算理论但不幸的是我的学校没有提供编译器构建课程.
我知道那里有讲座; 我希望能为特别好的产品提供建议.
还有新手到现场的书吗？除了龙书之外,至少还有一些东西.初学者水平很好,我知道市场上有很多中级高级文本.
谢谢!
有没有人对构建两个给定DFA的并集算法有直截了当的描述？例如,假设我们有两个DFA超过{0,1}
{w|w has an odd number of characters}
w has states A and B
delta | 0 | 1
----------------
A | B | B
----------------
B | A | A
{x|x has an even number of 1s}
x has states a and b
delta | 0 | 1
----------------
a | a | b
----------------
b | b | a
我有一个结果转换表显示联合:
delta | 0 | 1
----------------
Aa | Ba | Bb
----------------
Ab | Bb | Ba
---------------- …