Commits

Jan Lahoda  committed 1652365

Brute-force simulation of non-deterministic pushdown automaton (intended to cross-check results from other algorithms).

  • Participants
  • Parent commits a2b3031

Comments (0)

Files changed (4)

File src/info/lahoda/papers/code/NPDA.java

 
 import java.util.Collection;
 import java.util.Collections;
+import java.util.LinkedList;
+import java.util.List;
 import java.util.Map;
 import java.util.Set;
+import java.util.Stack;
 
 
 /**
         return transitionTable;
     }
 
+    /**Brute-force simulation of the non-deterministic pushdown automaton.
+s     */
+    public List<Integer> match(Iterable<? extends Character> inputIter) {
+        List<Integer> result = new LinkedList<Integer>();
+        StringBuilder inp = new StringBuilder();
+
+        for (char c : inputIter) {
+            inp.append(c);
+        }
+
+        char[] input = new char[inp.length()];
+
+        inp.getChars(0, inp.length(), input, 0);
+
+        List<SimulationState> todo = new LinkedList<SimulationState>();
+
+        for (int startingState : initialStates) {
+            Stack<Integer> pds = new Stack<Integer>();
+
+            pds.add(initialPushdownSymbol);
+
+            todo.add(new SimulationState(startingState, pds, 0));
+        }
+
+        while (!todo.isEmpty()) {
+            SimulationState state = todo.remove(0);
+
+            if (state.inputPos >= input.length) continue;
+            
+            handleTarget(state, input, Constants.epsilon, todo, result);
+            handleTarget(state, input, state.pushdownStore.pop(), todo, result);
+        }
+
+        Collections.sort(result);
+        
+        return result;
+    }
+
+    private void handleTarget(SimulationState state, char[] input, int pds1, List<SimulationState> todo, List<Integer> result) {
+        Collection<PDATarget> targetNotRemovingFromPDS = transitionTable.get(new PDAKey(state.state, input[state.inputPos], pds1));
+
+        if (targetNotRemovingFromPDS != null) {
+            for (PDATarget t : targetNotRemovingFromPDS) {
+                Stack<Integer> stack = new Stack<Integer>();
+
+                stack.addAll(state.pushdownStore);
+                if (t.pushDown != Constants.epsilon) {
+                    stack.push(t.pushDown);
+                }
+
+                todo.add(new SimulationState(t.state, stack, state.inputPos + 1));
+                
+                if (isFinal(t.state)) {
+                    result.add(state.inputPos + 1);
+                }
+            }
+        }
+    }
+
+    private static final class SimulationState {
+        private final int state;
+        private final Stack<Integer> pushdownStore;
+        private final int inputPos;
+
+        public SimulationState(int state, Stack<Integer> pushdownStore, int inputPos) {
+            this.state = state;
+            this.pushdownStore = pushdownStore;
+            this.inputPos = inputPos;
+        }
+        
+    }
 }
 

File test/info/lahoda/papers/code/DPDATest.java

 package info.lahoda.papers.code;
 
+import info.lahoda.papers.code.PDATestUtil.TestCase;
 import java.util.Arrays;
-import java.util.Collection;
-import java.util.HashMap;
-import java.util.HashSet;
 import java.util.List;
-import java.util.Map;
 import java.util.regex.Matcher;
 import java.util.regex.Pattern;
 import junit.framework.Assert;
 
     @Test
     public void testDeterminization() {
-        Map<PDAKey, Collection<PDATarget>> transitionTable = new HashMap<PDAKey, Collection<PDATarget>>();
+        for (TestCase tc : PDATestUtil.testCases()) {
+            DPDA dpda = DPDA.create(tc.automaton);
+            List<Integer> result = dpda.match(tc.input);
 
-        transitionTable.put(new PDAKey(0, 'x', Constants.epsilon), Arrays.asList(new PDATarget(0, Constants.epsilon), new PDATarget(1, Constants.epsilon)));
-        transitionTable.put(new PDAKey(0, 'd', Constants.epsilon), Arrays.asList(new PDATarget(0, 'd')));
-        transitionTable.put(new PDAKey(0, 'u', 'd'), Arrays.asList(new PDATarget(0, Constants.epsilon)));
-        
-        transitionTable.put(new PDAKey(1, 'd', Constants.epsilon), Arrays.asList(new PDATarget(2, 'd')));
-        transitionTable.put(new PDAKey(2, 'x', Constants.epsilon), Arrays.asList(new PDATarget(3, Constants.epsilon)));
-        transitionTable.put(new PDAKey(3, 'd', Constants.epsilon), Arrays.asList(new PDATarget(4, 'd')));
-        transitionTable.put(new PDAKey(4, 'x', Constants.epsilon), Arrays.asList(new PDATarget(5, Constants.epsilon)));
-        transitionTable.put(new PDAKey(5, 'u', 'd'), Arrays.asList(new PDATarget(6, Constants.epsilon)));
-        transitionTable.put(new PDAKey(6, 'x', Constants.epsilon), Arrays.asList(new PDATarget(7, Constants.epsilon)));
-        transitionTable.put(new PDAKey(7, 'u', 'd'), Arrays.asList(new PDATarget(8, Constants.epsilon)));
-        
-        NPDA npda = new NPDA(new HashSet<Integer>(Arrays.asList(0, 1, 2, 3, 4, 5, 6, 7, 8)), new char[] {'x', 'd', 'u'}, new HashSet<Integer>(Arrays.asList(Constants.nostate, (int)'d')), transitionTable, new HashSet<Integer>(Arrays.asList(0)), Constants.nostate, new HashSet<Integer>(Arrays.asList(8)));
-
-        DPDA dpda = DPDA.create(npda);
-        List<Integer> result = dpda.match(Arrays.<Character>asList('d', 'd', 'x', 'd', 'x', 'd', 'x', 'u', 'x', 'u', 'u', 'u'));
-
-        Assert.assertEquals(Arrays.asList(10), result);
+            Assert.assertEquals(tc.result, result);
+        }
     }
 
 //    @Test

File test/info/lahoda/papers/code/NPDATest.java

+package info.lahoda.papers.code;
+
+import info.lahoda.papers.code.PDATestUtil.TestCase;
+import java.util.List;
+import junit.framework.Assert;
+import org.junit.Test;
+
+/**
+ *
+ * @author lahvac
+ */
+public class NPDATest {
+
+    @Test
+    public void testSimulation() {
+        for (TestCase tc : PDATestUtil.testCases()) {
+            List<Integer> result = tc.automaton.match(tc.input);
+
+            Assert.assertEquals(tc.result, result);
+        }
+    }
+
+
+}

File test/info/lahoda/papers/code/PDATestUtil.java

+package info.lahoda.papers.code;
+
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Map;
+
+/**
+ *
+ * @author lahvac
+ */
+public class PDATestUtil {
+
+    public static Iterable<? extends TestCase> testCases() {
+        Map<PDAKey, Collection<PDATarget>> transitionTable = new HashMap<PDAKey, Collection<PDATarget>>();
+
+        transitionTable.put(new PDAKey(0, 'x', Constants.epsilon), Arrays.asList(new PDATarget(0, Constants.epsilon), new PDATarget(1, Constants.epsilon)));
+        transitionTable.put(new PDAKey(0, 'd', Constants.epsilon), Arrays.asList(new PDATarget(0, 'd')));
+        transitionTable.put(new PDAKey(0, 'u', 'd'), Arrays.asList(new PDATarget(0, Constants.epsilon)));
+
+        transitionTable.put(new PDAKey(1, 'd', Constants.epsilon), Arrays.asList(new PDATarget(2, 'd')));
+        transitionTable.put(new PDAKey(2, 'x', Constants.epsilon), Arrays.asList(new PDATarget(3, Constants.epsilon)));
+        transitionTable.put(new PDAKey(3, 'd', Constants.epsilon), Arrays.asList(new PDATarget(4, 'd')));
+        transitionTable.put(new PDAKey(4, 'x', Constants.epsilon), Arrays.asList(new PDATarget(5, Constants.epsilon)));
+        transitionTable.put(new PDAKey(5, 'u', 'd'), Arrays.asList(new PDATarget(6, Constants.epsilon)));
+        transitionTable.put(new PDAKey(6, 'x', Constants.epsilon), Arrays.asList(new PDATarget(7, Constants.epsilon)));
+        transitionTable.put(new PDAKey(7, 'u', 'd'), Arrays.asList(new PDATarget(8, Constants.epsilon)));
+
+        NPDA npda = new NPDA(new HashSet<Integer>(Arrays.asList(0, 1, 2, 3, 4, 5, 6, 7, 8)), new char[] {'x', 'd', 'u'}, new HashSet<Integer>(Arrays.asList(Constants.nostate, (int)'d')), transitionTable, new HashSet<Integer>(Arrays.asList(0)), Constants.nostate, new HashSet<Integer>(Arrays.asList(8)));
+        List<Character> input = Arrays.<Character>asList('d', 'd', 'x', 'd', 'x', 'd', 'x', 'u', 'x', 'u', 'u', 'u');
+        List<Integer> result = Arrays.asList(10);
+
+        return Arrays.asList(
+                new TestCase(npda, input, result)
+        );
+    }
+
+    public static final class TestCase {
+        public final NPDA automaton;
+        public final Iterable<? extends Character> input;
+        public final List<Integer> result;
+
+        public TestCase(NPDA automaton, Iterable<? extends Character> input, List<Integer> result) {
+            this.automaton = automaton;
+            this.input = input;
+            this.result = result;
+        }
+        
+    }
+}