@Test public void basicTest() { String regex = "(d|e)*(a|b.|c)+g"; ExtensionNFA nfa = new ExtensionNFA(regex); Assert.assertTrue(nfa.recognizes("ag")); Assert.assertTrue(nfa.recognizes("bcg")); Assert.assertTrue(nfa.recognizes("cg")); Assert.assertTrue(nfa.recognizes("bzg")); Assert.assertTrue(nfa.recognizes("dag")); Assert.assertTrue(nfa.recognizes("decg")); Assert.assertTrue(nfa.recognizes("eeecg")); Assert.assertTrue(nfa.recognizes("dddb0g")); Assert.assertTrue(nfa.recognizes("eabbbeag")); Assert.assertFalse(nfa.recognizes("adg")); Assert.assertFalse(nfa.recognizes("")); Assert.assertFalse(nfa.recognizes("deg")); Assert.assertFalse(nfa.recognizes("eeg")); Assert.assertFalse(nfa.recognizes("ab")); Assert.assertFalse(nfa.recognizes("bbb")); Assert.assertFalse(nfa.recognizes("b")); Assert.assertFalse(nfa.recognizes("d")); }
public boolean recognizes(String txt) { DirectedDFS dfs = new DirectedDFS(graph, 0); Bag<Integer> pc = new Bag<Integer>(); for (int v = 0; v < graph.V(); v++) if (dfs.marked(v)) pc.add(v); for (int i = 0; i < txt.length(); i++) { if (txt.charAt(i) == '+' || txt.charAt(i) == '*' || txt.charAt(i) == '|' || txt.charAt(i) == '(' || txt.charAt(i) == ')') throw new IllegalArgumentException("text contains the metacharacter '" + txt.charAt(i) + "'"); Bag<Integer> match = new Bag<Integer>(); for (int v : pc) { if (v == m) continue; if ((regexp.charAt(v) == txt.charAt(i)) || regexp.charAt(v) == '.') match.add(v + 1); } dfs = new DirectedDFS(graph, match); pc = new Bag<Integer>(); for (int v = 0; v < graph.V(); v++) if (dfs.marked(v)) pc.add(v); if (pc.size() == 0) return false; } for (int v : pc) if (v == m) return true; return false; }
ExtensionNFA { public boolean recognizes(String txt) { DirectedDFS dfs = new DirectedDFS(graph, 0); Bag<Integer> pc = new Bag<Integer>(); for (int v = 0; v < graph.V(); v++) if (dfs.marked(v)) pc.add(v); for (int i = 0; i < txt.length(); i++) { if (txt.charAt(i) == '+' || txt.charAt(i) == '*' || txt.charAt(i) == '|' || txt.charAt(i) == '(' || txt.charAt(i) == ')') throw new IllegalArgumentException("text contains the metacharacter '" + txt.charAt(i) + "'"); Bag<Integer> match = new Bag<Integer>(); for (int v : pc) { if (v == m) continue; if ((regexp.charAt(v) == txt.charAt(i)) || regexp.charAt(v) == '.') match.add(v + 1); } dfs = new DirectedDFS(graph, match); pc = new Bag<Integer>(); for (int v = 0; v < graph.V(); v++) if (dfs.marked(v)) pc.add(v); if (pc.size() == 0) return false; } for (int v : pc) if (v == m) return true; return false; } }
ExtensionNFA { public boolean recognizes(String txt) { DirectedDFS dfs = new DirectedDFS(graph, 0); Bag<Integer> pc = new Bag<Integer>(); for (int v = 0; v < graph.V(); v++) if (dfs.marked(v)) pc.add(v); for (int i = 0; i < txt.length(); i++) { if (txt.charAt(i) == '+' || txt.charAt(i) == '*' || txt.charAt(i) == '|' || txt.charAt(i) == '(' || txt.charAt(i) == ')') throw new IllegalArgumentException("text contains the metacharacter '" + txt.charAt(i) + "'"); Bag<Integer> match = new Bag<Integer>(); for (int v : pc) { if (v == m) continue; if ((regexp.charAt(v) == txt.charAt(i)) || regexp.charAt(v) == '.') match.add(v + 1); } dfs = new DirectedDFS(graph, match); pc = new Bag<Integer>(); for (int v = 0; v < graph.V(); v++) if (dfs.marked(v)) pc.add(v); if (pc.size() == 0) return false; } for (int v : pc) if (v == m) return true; return false; } ExtensionNFA(String regexp); }
ExtensionNFA { public boolean recognizes(String txt) { DirectedDFS dfs = new DirectedDFS(graph, 0); Bag<Integer> pc = new Bag<Integer>(); for (int v = 0; v < graph.V(); v++) if (dfs.marked(v)) pc.add(v); for (int i = 0; i < txt.length(); i++) { if (txt.charAt(i) == '+' || txt.charAt(i) == '*' || txt.charAt(i) == '|' || txt.charAt(i) == '(' || txt.charAt(i) == ')') throw new IllegalArgumentException("text contains the metacharacter '" + txt.charAt(i) + "'"); Bag<Integer> match = new Bag<Integer>(); for (int v : pc) { if (v == m) continue; if ((regexp.charAt(v) == txt.charAt(i)) || regexp.charAt(v) == '.') match.add(v + 1); } dfs = new DirectedDFS(graph, match); pc = new Bag<Integer>(); for (int v = 0; v < graph.V(); v++) if (dfs.marked(v)) pc.add(v); if (pc.size() == 0) return false; } for (int v : pc) if (v == m) return true; return false; } ExtensionNFA(String regexp); boolean recognizes(String txt); static void main(String[] args); }
ExtensionNFA { public boolean recognizes(String txt) { DirectedDFS dfs = new DirectedDFS(graph, 0); Bag<Integer> pc = new Bag<Integer>(); for (int v = 0; v < graph.V(); v++) if (dfs.marked(v)) pc.add(v); for (int i = 0; i < txt.length(); i++) { if (txt.charAt(i) == '+' || txt.charAt(i) == '*' || txt.charAt(i) == '|' || txt.charAt(i) == '(' || txt.charAt(i) == ')') throw new IllegalArgumentException("text contains the metacharacter '" + txt.charAt(i) + "'"); Bag<Integer> match = new Bag<Integer>(); for (int v : pc) { if (v == m) continue; if ((regexp.charAt(v) == txt.charAt(i)) || regexp.charAt(v) == '.') match.add(v + 1); } dfs = new DirectedDFS(graph, match); pc = new Bag<Integer>(); for (int v = 0; v < graph.V(); v++) if (dfs.marked(v)) pc.add(v); if (pc.size() == 0) return false; } for (int v : pc) if (v == m) return true; return false; } ExtensionNFA(String regexp); boolean recognizes(String txt); static void main(String[] args);  }