Closed sergey-v-galtsev closed 12 years ago
Dumped FSMs look like the following. (After passing this through 'dot' it is obvious that some states are dangling. E.g. in "NFA for: /^.$/" states 1 and 7 can not be reached from initial state 9.)
digraph { "initial"[shape="plaintext",label="NFA for: /^.$/"] 0[shape="circle",label="0"] 0 -> 2[label="^"] 1[shape="circle",label="1"] 1 -> 2[label="^"] 2[shape="circle",label="2"] 2 -> 3[label="[\\360-\\367]"] 2 -> 4[label="[\\340-\\357]"] 2 -> 5[label="[\\300-\\337]"] 2 -> 6[label="^ $ [\\000-\\177]"] 3[shape="circle",label="3"] 3 -> 4[label="[\\200-\\277]"] 4[shape="circle",label="4"] 4 -> 5[label="[\\200-\\277]"] 5[shape="circle",label="5"] 5 -> 6[label="[\\200-\\277]"] 6[shape="circle",label="6"] 6 -> 8[label="$"] 7[shape="circle",label="7"] 7 -> 8[label="$"] 8[shape="circle",label="8"] 8 -> 10[label="<Epsilon>"] 9[shape="circle",label="9"] "initial" -> 9 9 -> 0[label="<Epsilon>"] 9 -> 9[label="<Epsilon> ^ $ ."] 10[shape="doublecircle",label="10"] 10 -> 10[label="<Epsilon> ^ $ ."] } digraph { "initial"[shape="plaintext",label="DFA for: /^.$/"] 0[shape="circle",label=""] "initial" -> 0 0 -> 0[label="$ ."] 0 -> 4[label="^"] 1[shape="doublecircle",label=""] 1 -> 1[label="^ $ ."] 2[shape="circle",label=""] 2 -> 0[label="."] 2 -> 1[label="$"] 2 -> 4[label="^"] 3[shape="circle",label=""] 3 -> 0[label="$ [^\\200-\\277]"] 3 -> 2[label="[\\200-\\277]"] 3 -> 4[label="^"] 4[shape="circle",label=""] 4 -> 0[label="[\\200-\\277\\370-\\377]"] 4 -> 2[label="$ [\\000-\\177]"] 4 -> 3[label="[\\300-\\337]"] 4 -> 5[label="^"] 4 -> 6[label="[\\340-\\357]"] 4 -> 7[label="[\\360-\\367]"] 5[shape="circle",label=""] 5 -> 0[label="[\\200-\\277\\370-\\377]"] 5 -> 1[label="$"] 5 -> 2[label="[\\000-\\177]"] 5 -> 3[label="[\\300-\\337]"] 5 -> 5[label="^"] 5 -> 6[label="[\\340-\\357]"] 5 -> 7[label="[\\360-\\367]"] 6[shape="circle",label=""] 6 -> 0[label="$ [^\\200-\\277]"] 6 -> 3[label="[\\200-\\277]"] 6 -> 4[label="^"] 7[shape="circle",label=""] 7 -> 0[label="$ [^\\200-\\277]"] 7 -> 4[label="^"] 7 -> 6[label="[\\200-\\277]"] } digraph { "initial"[shape="plaintext",label="NFA for: /^hello$/yi"] 0[shape="circle",label="0"] 0 -> 2[label="^"] 1[shape="circle",label="1"] 1 -> 2[label="^"] 2[shape="circle",label="2"] 2 -> 3[label="[Hh]"] 2 -> 4[label="[\\320]"] 3[shape="circle",label="3"] 3 -> 5[label="[Ee]"] 3 -> 6[label="[\\320]"] 3 -> 7[label="[\\321]"] 4[shape="circle",label="4"] 4 -> 3[label="[\\235]"] 5[shape="circle",label="5"] 5 -> 8[label="[Ll]"] 6[shape="circle",label="6"] 6 -> 5[label="[\\201\\225\\265]"] 7[shape="circle",label="7"] 7 -> 5[label="[\\221]"] 8[shape="circle",label="8"] 8 -> 9[label="[Ll]"] 9[shape="circle",label="9"] 9 -> 10[label="[Oo]"] 9 -> 11[label="[\\320]"] 10[shape="circle",label="10"] 10 -> 13[label="$"] 11[shape="circle",label="11"] 11 -> 10[label="[\\236\\276]"] 12[shape="circle",label="12"] 12 -> 13[label="$"] 13[shape="circle",label="13"] 13 -> 15[label="<Epsilon>"] 14[shape="circle",label="14"] "initial" -> 14 14 -> 0[label="<Epsilon>"] 14 -> 14[label="<Epsilon> ^ $ ."] 15[shape="doublecircle",label="15"] 15 -> 15[label="<Epsilon> ^ $ ."] } digraph { "initial"[shape="plaintext",label="DFA for: /^hello$/yi"] 0[shape="circle",label=""] "initial" -> 0 0 -> 0[label="$ ."] 0 -> 10[label="^"] 1[shape="doublecircle",label=""] 1 -> 1[label="^ $ ."] 2[shape="circle",label=""] 2 -> 0[label="."] 2 -> 1[label="$"] 2 -> 10[label="^"] 3[shape="circle",label=""] 3 -> 0[label="$ [^Oo\\320]"] 3 -> 2[label="[Oo]"] 3 -> 4[label="[\\320]"] 3 -> 10[label="^"] 4[shape="circle",label=""] 4 -> 0[label="$ [^\\236\\276]"] 4 -> 2[label="[\\236\\276]"] 4 -> 10[label="^"] 5[shape="circle",label=""] 5 -> 0[label="$ [^Ll]"] 5 -> 3[label="[Ll]"] 5 -> 10[label="^"] 6[shape="circle",label=""] 6 -> 0[label="$ [^Ll]"] 6 -> 5[label="[Ll]"] 6 -> 10[label="^"] 7[shape="circle",label=""] 7 -> 0[label="$ [^Ee\\320-\\321]"] 7 -> 6[label="[Ee]"] 7 -> 8[label="[\\321]"] 7 -> 9[label="[\\320]"] 7 -> 10[label="^"] 8[shape="circle",label=""] 8 -> 0[label="$ [^\\221]"] 8 -> 6[label="[\\221]"] 8 -> 10[label="^"] 9[shape="circle",label=""] 9 -> 0[label="$ [^\\201\\225\\265]"] 9 -> 6[label="[\\201\\225\\265]"] 9 -> 10[label="^"] 10[shape="circle",label=""] 10 -> 0[label="$ [^Hh\\320]"] 10 -> 7[label="[Hh]"] 10 -> 10[label="^"] 10 -> 11[label="[\\320]"] 11[shape="circle",label=""] 11 -> 0[label="$ [^\\235]"] 11 -> 7[label="[\\235]"] 11 -> 10[label="^"] } digraph { "initial"[shape="plaintext",label="NFA for: /^hello$/w"] 0[shape="circle",label="0"] 0 -> 2[label="^"] 1[shape="circle",label="1"] 1 -> 2[label="^"] 2[shape="circle",label="2"] 2 -> 5[label="[h]"] 3[shape="circle",label="3"] 3 -> 5[label="[h]"] 4[shape="circle",label="4"] 4 -> 5[label="[h]"] 5[shape="circle",label="5"] 5 -> 8[label="[e]"] 6[shape="circle",label="6"] 6 -> 8[label="[e]"] 7[shape="circle",label="7"] 7 -> 8[label="[e]"] 8[shape="circle",label="8"] 8 -> 11[label="[l]"] 9[shape="circle",label="9"] 9 -> 11[label="[l]"] 10[shape="circle",label="10"] 10 -> 11[label="[l]"] 11[shape="circle",label="11"] 11 -> 14[label="[l]"] 12[shape="circle",label="12"] 12 -> 14[label="[l]"] 13[shape="circle",label="13"] 13 -> 14[label="[l]"] 14[shape="circle",label="14"] 14 -> 17[label="[o]"] 15[shape="circle",label="15"] 15 -> 17[label="[o]"] 16[shape="circle",label="16"] 16 -> 17[label="[o]"] 17[shape="circle",label="17"] 17 -> 19[label="$"] 18[shape="circle",label="18"] 18 -> 19[label="$"] 19[shape="circle",label="19"] 19 -> 21[label="<Epsilon>"] 20[shape="circle",label="20"] "initial" -> 20 20 -> 0[label="<Epsilon>"] 20 -> 20[label="<Epsilon> ^ $ ."] 21[shape="doublecircle",label="21"] 21 -> 21[label="<Epsilon> ^ $ ."] } digraph { "initial"[shape="plaintext",label="DFA for: /^hello$/w"] 0[shape="circle",label=""] "initial" -> 0 0 -> 0[label="$ ."] 0 -> 7[label="^"] 1[shape="doublecircle",label=""] 1 -> 1[label="^ $ ."] 2[shape="circle",label=""] 2 -> 0[label="."] 2 -> 1[label="$"] 2 -> 7[label="^"] 3[shape="circle",label=""] 3 -> 0[label="$ [^o]"] 3 -> 2[label="[o]"] 3 -> 7[label="^"] 4[shape="circle",label=""] 4 -> 0[label="$ [^l]"] 4 -> 3[label="[l]"] 4 -> 7[label="^"] 5[shape="circle",label=""] 5 -> 0[label="$ [^l]"] 5 -> 4[label="[l]"] 5 -> 7[label="^"] 6[shape="circle",label=""] 6 -> 0[label="$ [^e]"] 6 -> 5[label="[e]"] 6 -> 7[label="^"] 7[shape="circle",label=""] 7 -> 0[label="$ [^h]"] 7 -> 6[label="[h]"] 7 -> 7[label="^"] } digraph { "initial"[shape="plaintext",label="DFA for capture: /id = \"([0-9]+)\"/"] 0[shape="circle",label=""] "initial" -> 0 0 -> 0[label="^ $ [^i]"] 0 -> 8[label="[i]"] 1[shape="doublecircle",label=""] 1 -> 1[label="^ $ ."] 2[shape="circle",label=""] 2 -> 0[label="^ $ [^\"0-9i]"] 2 -> 1[label="[\"] (outputs: 1)"] 2 -> 2[label="[0-9]"] 2 -> 8[label="[i]"] 3[shape="circle",label=""] 3 -> 0[label="^ $ [^0-9i]"] 3 -> 2[label="[0-9] (outputs: 0)"] 3 -> 8[label="[i]"] 4[shape="circle",label=""] 4 -> 0[label="^ $ [^\"i]"] 4 -> 3[label="[\"]"] 4 -> 8[label="[i]"] 5[shape="circle",label=""] 5 -> 0[label="^ $ [^ i]"] 5 -> 4[label="[ ]"] 5 -> 8[label="[i]"] 6[shape="circle",label=""] 6 -> 0[label="^ $ [^=i]"] 6 -> 5[label="[=]"] 6 -> 8[label="[i]"] 7[shape="circle",label=""] 7 -> 0[label="^ $ [^ i]"] 7 -> 6[label="[ ]"] 7 -> 8[label="[i]"] 8[shape="circle",label=""] 8 -> 0[label="^ $ [^di]"] 8 -> 7[label="[d]"] 8 -> 8[label="[i]"] }
Dumped FSMs look like the following. (After passing this through 'dot' it is obvious that some states are dangling. E.g. in "NFA for: /^.$/" states 1 and 7 can not be reached from initial state 9.)