Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP

Comparing changes

Choose two branches to see what's changed or to start a new pull request. If you need to, you can also compare across forks.

Open a pull request

Create a new pull request by comparing changes across two branches. If you need to, you can also compare across forks.
base fork: davidsantiago/swangee
base: master
...
head fork: davidsantiago/swangee
compare: develop
Checking mergeability… Don't worry, you can still create the pull request.
  • 19 commits
  • 9 files changed
  • 0 commit comments
  • 1 contributor
Commits on Mar 14, 2011
@davidsantiago Remove error about clojure.com/complement being overridden in swangee…
….core.
b65dfed
Commits on Mar 15, 2011
@davidsantiago Change definition of NFA to have transitions be a map of states to ma…
…ps of symbols to states. Updated docs and tests to match.
f83bc1a
@davidsantiago Added epsilon-closure function to calculate the epsilon-closure of an…
… NFA state. Added tests for same.
733ac2c
@davidsantiago Changed NFA's step function implementation to move from the epsilon-c…
…losure of a state, instead of just the state.
64e1ee1
Commits on Mar 16, 2011
@davidsantiago Split NFA and DFA into their own namespaces. Also split their respect…
…ive tests into their own test namespaces.
9d6bb46
@davidsantiago Add a more robust test for NFA with epsilon-transitions. This test ac…
…tually simulates the run of an NFA with epsilon transitions, instead of just testing the epsilon-closure funciton.
785b19c
@davidsantiago Small fix to epsilon-closure so that it works with states that aren't…
… given as sets.
4a08017
@davidsantiago Added tests to epsilon-closure to test functionality with states that…
… aren't in sets and also the epsilon closure of a set of states.
1131f41
@davidsantiago Improved comments about the language being tested in tests. 7f252aa
Commits on Mar 17, 2011
@davidsantiago Added swangee.conversions function with determinize function to do nf…
…a->dfa conversion. Also tests.
b1450fb
Commits on Mar 18, 2011
@davidsantiago Some reorganization of tests to centralize the language definitions a…
…nd make the testing macros more generically applicable. Currently a test failing due to problem in swangee.core/match, will fix subsequently.
87004d9
@davidsantiago Rewrote swangee.core/match, it was totally broken. Should be slightly…
… less broken now. All tests pass.
34287bd
@davidsantiago Rewrote swangee.core/run after noticing that it was messed up similar…
…ly to match. Reads nicer now, more confidence in the code, all tests pass.
a3eb16a
@davidsantiago Fixed bugs in the NFA implementation of valid-state? and accepting-st…
…ate?; were not properly updated to account for addition of epsilon transition support.
e1c9480
@davidsantiago Additional tests and fixes for improperly written tests. 82c6719
@davidsantiago Added DFAs for langs 2 and 3 and updated DFA tests to run tests on th…
…ose languages.
9781cd5
@davidsantiago Fixes to move-nfa and outgoing-symbols in nfa.clj to prevent exceptio…
…ns when trying to create a set from a seq with duplicates.
7991021
@davidsantiago Add tests for determinization of an nfa. 80a15e1
Commits on Mar 23, 2012
@davidsantiago Add citation to comment for subset construction algorithm. aa6d6bb
View
41 src/swangee/conversions.clj
@@ -0,0 +1,41 @@
+(ns swangee.conversions
+ (:refer-clojure :exclude [complement])
+ (:use [swangee core nfa dfa])
+ (:require [swangee.core :as swangee]
+ [clojure.set :as set]))
+
+(defn determinize
+ "Converts the given NFA into a DFA using Buchi's (subset construction)
+ algorithm. For example, see Aho, Sethi & Ullman Algorithm 3.2 or
+ http://web.cecs.pdx.edu/~harry/compilers/slides/LexicalPart3.pdf"
+ [nfa]
+ ;; First save the "name" (a set of nfa states) of the initial state
+ ;; for the final call to make the dfa.
+ (let [initial-state (epsilon-closure (:transitions nfa)
+ (:initial-state nfa))]
+ (loop [dfa-states {} ;; Map of sets of nfa states to compiled-states
+ unmarked-states #{initial-state}] ;; Set of sets of nfa states.
+ (if-let [dfa-state (first unmarked-states)] ;; dfa-state is a set.
+ (let [dfa-state-trans
+ (into {} (for [sym (outgoing-symbols nfa dfa-state)]
+ ;; For every symbol that has a transition out, add
+ ;; a transition to the set of possible nfa states that
+ ;; the nfa is in after seeing that input.
+ [sym (epsilon-closure (:transitions nfa)
+ (move-nfa nfa dfa-state sym))]))
+ ;; Will set this dfa state to be final if any primitive nfa state
+ ;; is final.
+ accepting? (accepting-state? nfa dfa-state)]
+ (recur (conj dfa-states [dfa-state (compiled-state dfa-state-trans
+ accepting?)])
+ ;; Only add into unmarked-states the new states we built as
+ ;; sets of possible destinations that haven't already been
+ ;; added to the final dfa. Final DFA state "names" are sets
+ ;; in the keys of the dfa-states map, and values in the
+ ;; map of this particular new state's transitions map.
+ (set/union (rest unmarked-states)
+ (set/difference (apply hash-set
+ (vals dfa-state-trans))
+ (apply hash-set (keys dfa-states))))))
+ ;; if-let failed: ran out of unmarked states. Finish up and return.
+ (dfa :states dfa-states :initial-state initial-state)))))
View
143 src/swangee/core.clj
@@ -1,4 +1,5 @@
(ns swangee.core
+ (:refer-clojure :exclude [complement])
(:require [clojure.set :as set])
(:use swangee.utils))
@@ -36,136 +37,38 @@
;; Initial state. NFA: I = #{x,...}
;; DFA: I = x
-;; For an NFA:
-;; Transition function (Q -> (E -> P(Q))). Can return a state or
-;; a collection of states.
-;; Initial state: A state or collection of states.
-;; Configuration: Collection of states & input sequence.
-(defrecord NFA [states ;; A collection of states
- transitions ;; A collection of transition functions.
- initial-state ;; One of the identifiers in states.
- accepting-states] ;; A set of states in the state member.
- FiniteAutomaton
- (initial-state [this] (:initial-state this))
- (accepting-state? [this state]
- (not (empty? (set/intersection state
- (:accepting-states this)))))
- (valid-state? [this state] (not (empty? (set/intersection state (:states this)))))
- (step [this {:keys [state input]}]
- ;; Have to apply every function in the collection of transitions to the state,
- ;; then apply the results of that to every state in the current state.
- ;; Calling hash-set just once is much faster than set/union on a bunch of
- ;; smaller hash-sets.
- (Configuration. (apply hash-set
- (apply concat (for [f (:transitions this)
- s state]
- (as-coll
- ((or (f s)
- (constantly nil)) (first input))))))
- (rest input)))
-
- ComposableAutomaton
- (complement [this] (NFA. (:states this)
- (:transitions this)
- (:initial-state this)
- ;; Next line is key: Turn all non-accepting states into
- ;; accepting states and vice versa.
- (set/difference (:states this)
- (:accepting-states this)))))
-
-(defn nfa
- "Takes arguments for states, transitions, and initial state to construct
- an nfa."
- [& rest]
- (let [{:keys [states transitions initial-state accepting-states]} (apply hash-map rest)]
- (NFA. (apply hash-set states)
- transitions
- initial-state
- (apply hash-set accepting-states))))
-
-;; NFAs are much nicer and easier to work with, but DFAs are much faster to
-;; simulate. You can, of course, express a DFA as an NFA, so for building and
-;; messing around, an NFA is usually best. Convert to a DFA if you want. But we
-;; need a lower-level DFA construct.
-;;
-;; In our DFA, a state is an object containing its outbound transitions and
-;; a flag indicating whether it is an accepting state. A transition is a function
-;; of an input that return the next state. We don't accept a list of such, we
-;; only work with a "compiled" transition function that we apply once to get
-;; the answer. Again, no assumption of such, but a map of inputs to states is
-;; a great, fast way to do this that remains easily modifiable. Also, note that
-;; a transition returns the state object itself, not its name.
-
-;; A state object that contains its transitions (function of input only)
-;; and a flag for whether this is an accepting state.
-(defrecord CompiledState [transitions accepting?])
-
-(defn compiled-state
- "A convenient constructor for a compiled state."
- [transitions accepting?]
- (CompiledState. transitions accepting?))
-
-;; For a DFA:
-;; Transition function (E -> Q). Only returns a state.
-;; Initial state: A single initial state.
-;; Configuration: A state and input sequence.
-
-(defrecord DFA [states ;; A map of 'names' (whatever) to states.
- initial-state] ;; A single initial state, a member of states.
- FiniteAutomaton
- (initial-state [this] (:initial-state this))
- (accepting-state? [this state] (boolean (:accepting? ((:states this) state))))
- (valid-state? [this state] (contains? (:states this) state))
- (step [this {:keys [state input]}]
- (Configuration. ((or (:transitions ((:states this) state)
- (constantly nil))) (first input))
- (rest input))))
-
-(defn dfa
- "Takes arguments for states, and initial state to construct
- a dfa."
- [& rest]
- (let [{:keys [states initial-state]} (apply hash-map rest)]
- (DFA. states
- initial-state)))
-
;;
;; Core operations
;;
(defn run
- "Given a FiniteAutomaton and an input sequence, returns true (accept) or false."
+ "Given a FiniteAutomaton and an input sequence, return true (accept) or false."
[^FiniteAutomaton fa input]
- (loop [curr-cfg (config (initial-state fa)
- input)]
- (let [next-cfg (step fa curr-cfg)]
- (if (not (valid-state? fa (:state next-cfg))) ;; Was no valid transition...
- false
- (if (empty? (:input next-cfg)) ;; Ran out of input, return based on final state.
- (accepting-state? fa (:state next-cfg))
- (recur next-cfg)))))) ;; Still have input, so recur.
+ (loop [curr-cfg (config (initial-state fa) input)]
+ (if (not (valid-state? fa (:state curr-cfg))) ;; Was not a valid transition
+ false
+ (if (empty? (:input curr-cfg)) ;; Ran out of input, return on final state.
+ (accepting-state? fa (:state curr-cfg))
+ (recur (step fa curr-cfg)))))) ;; Still have input, so recur.
(defn match
- "Given a FiniteAutomaton and an input sequence, return the longest string matched
- starting on the first character of the string."
+ "Given a FiniteAutomaton and an input sequence, return the longest string
+ matched starting on the first character of the string."
[^FiniteAutomaton fa input]
- (loop [curr-cfg (config (initial-state fa)
- input)
- symbols-seen [(first input)]
+ (loop [curr-cfg (config (initial-state fa) input)
+ symbols-seen []
longest-match []]
- (let [next-cfg (step fa curr-cfg)]
- (if (not (valid-state? fa (:state next-cfg))) ;; No route to acceptance...
+ (if (not (valid-state? fa (:state curr-cfg)))
+ longest-match ;; No route to acceptance, just return longest-match.
+ ;; The state is valid, so process further.
+ (if (empty? (:input curr-cfg))
longest-match
- (if (empty? (:input next-cfg)) ;; Out of input, return depends on state.
- (if (accepting-state? fa (:state next-cfg)) ;; If we are in accepting state,
- (conj longest-match (first (:input curr-cfg))) ;; Add last input we saw and return.
- ;; Otherwise, we are out of input but not in accepting, state...
- longest-match)
- ;; Not out of input, so continue...
+ ;; Not out of input, so continue...
+ (let [next-cfg (step fa curr-cfg)
+ next-symbols-seen (conj symbols-seen (first (:input curr-cfg)))]
(recur next-cfg
- (conj symbols-seen (first (:input next-cfg)))
- ;; Only set longest-match to symbols seen if we're in accepting state.
+ next-symbols-seen
+ ;; Only add to longest-match if we are in an accepting state.
(if (accepting-state? fa (:state next-cfg))
- symbols-seen
- longest-match)))))))
-
+ next-symbols-seen
+ longest-match)))))))
View
50 src/swangee/dfa.clj
@@ -0,0 +1,50 @@
+(ns swangee.dfa
+ (:refer-clojure :exclude [complement])
+ (:require [clojure.set :as set])
+ (:use [swangee core utils]))
+
+;; NFAs are much nicer and easier to work with, but DFAs are much faster to
+;; simulate. You can, of course, express a DFA as an NFA, so for building and
+;; messing around, an NFA is usually best. Convert to a DFA if you want. But we
+;; need a lower-level DFA construct.
+;;
+;; In our DFA, a state is an object containing its outbound transitions and
+;; a flag indicating whether it is an accepting state. A transition is a function
+;; of an input that return the next state. We don't accept a list of such, we
+;; only work with a "compiled" transition function that we apply once to get
+;; the answer. Again, no assumption of such, but a map of inputs to states is
+;; a great, fast way to do this that remains easily modifiable. Also, note that
+;; a transition returns the state object itself, not its name.
+
+;; A state object that contains its transitions (function of input only)
+;; and a flag for whether this is an accepting state.
+(defrecord CompiledState [transitions accepting?])
+
+(defn compiled-state
+ "A convenient constructor for a compiled state."
+ [transitions accepting?]
+ (CompiledState. transitions accepting?))
+
+;; For a DFA:
+;; Transition function (E -> Q). Only returns a state.
+;; Initial state: A single initial state.
+;; Configuration: A state and input sequence.
+
+(defrecord DFA [states ;; A map of 'names' (whatever) to states.
+ initial-state] ;; A single initial state, a member of states.
+ FiniteAutomaton
+ (initial-state [this] (:initial-state this))
+ (accepting-state? [this state] (boolean (:accepting? ((:states this) state))))
+ (valid-state? [this state] (contains? (:states this) state))
+ (step [this {:keys [state input]}]
+ (config ((or (:transitions ((:states this) state)
+ (constantly nil))) (first input))
+ (rest input))))
+
+(defn dfa
+ "Takes arguments for states, and initial state to construct
+ a dfa."
+ [& rest]
+ (let [{:keys [states initial-state]} (apply hash-map rest)]
+ (DFA. states
+ initial-state)))
View
100 src/swangee/nfa.clj
@@ -0,0 +1,100 @@
+(ns swangee.nfa
+ (:refer-clojure :exclude [complement])
+ (:require [clojure.set :as set])
+ (:use [swangee core utils]))
+
+(defn epsilon-closure
+ "Given an NFA's transition function (A map of states to maps of inputs to
+ states), and a state, returns the epsilon closure of that state."
+ [transitions state]
+ (loop [e-closure (into #{} (as-coll state))] ;; Start with the state itself.
+ (let [e-reachable-states
+ (apply concat
+ (filter #(not (nil? %))
+ (map #(as-coll (get (transitions %) nil))
+ e-closure)))
+ next-e-closure (into e-closure e-reachable-states)]
+ (if (= next-e-closure e-closure)
+ e-closure
+ (recur next-e-closure)))))
+
+;; For an NFA:
+;; Transition function (Q -> (E -> P(Q))). Can return a state or
+;; a collection of states. *Make sure this is a map of states to a map of
+;; input symbols to state/state collection*.
+;; Initial state: A state or collection of states.
+;; Configuration: Collection of states & input sequence.
+;;
+;; An epsilon transition takes nil as input, but is otherwise like every other
+;; transition.
+(defrecord NFA [states ;; A collection of states
+ transitions ;; A transition function (see above).
+ initial-state ;; One of the identifiers in states.
+ accepting-states] ;; A set of states in the state member.
+ FiniteAutomaton
+ (initial-state [this] (:initial-state this))
+ (accepting-state? [this state]
+ (not (empty? (set/intersection
+ (epsilon-closure (:transitions this) state)
+ (:accepting-states this)))))
+ (valid-state? [this state]
+ (not (empty? (set/intersection
+ (epsilon-closure (:transitions this) state)
+ (:states this)))))
+ (step [this {:keys [state input]}]
+ ;; Have to apply transition to every primitive state in the state, then
+ ;; apply all of those to the input symbol, collecting the answer states
+ ;; together at the end. Calling hash-set just once is much faster than
+ ;; set/union on a bunch of smaller hash-sets.
+ (config
+ (apply hash-set
+ (apply concat (for [s (epsilon-closure (:transitions this)
+ state)]
+ (as-coll
+ ((or ((:transitions this) s)
+ (constantly nil)) (first input))))))
+ (rest input)))
+
+ ComposableAutomaton
+ (complement [this] (NFA. (:states this)
+ (:transitions this)
+ (:initial-state this)
+ ;; Next line is key: Turn all non-accepting states
+ ;; into accepting states and vice versa.
+ (set/difference (:states this)
+ (:accepting-states this)))))
+
+(defn nfa
+ "Takes arguments for states, transitions, and initial state to construct
+ an nfa."
+ [& rest]
+ (let [{:keys [states transitions initial-state accepting-states]}
+ (apply hash-map rest)]
+ (NFA. (apply hash-set states)
+ transitions
+ initial-state
+ (apply hash-set accepting-states))))
+
+;;
+;; NFA-specific operations
+;;
+
+(defn move-nfa
+ "Given a set of states, returns the set of states that can possibly be reached
+ by consuming the given input symbol. Note that epsilon (nil) doesn't count
+ as an input symbol here."
+ [nfa state-set input]
+ (into #{}
+ (apply concat (map #(as-coll (get ((:transitions nfa) %) input))
+ (epsilon-closure (:transitions nfa)
+ state-set)))))
+
+(defn outgoing-symbols
+ "Given an nfa and a set of states, returns the set of input symbols that
+ have transitions defined. Note that epsilon (nil) doesn't count as an
+ input symbol here."
+ [nfa state-set]
+ (into #{}
+ (apply concat (for [state state-set]
+ (filter #(not (nil? %))
+ (keys ((:transitions nfa) state)))))))
View
16 test/swangee/conversions_test.clj
@@ -0,0 +1,16 @@
+(ns swangee.conversions-test
+ (:use clojure.test
+ swangee.core-test
+ [swangee test-automata-defs nfa dfa conversions])
+ (:require [swangee.core :as swangee]))
+
+;;
+;; Test determinization of an NFA.
+;;
+(test-basic-run (determinize lang1-nfa) lang1-strings not-lang1-strings)
+(test-basic-run (determinize lang2-nfa) lang2-strings not-lang2-strings)
+(test-basic-run (determinize lang3-nfa) lang3-strings not-lang3-strings)
+
+(test-basic-match (determinize lang1-nfa) lang1-string-matches)
+(test-basic-match (determinize lang2-nfa) lang2-string-matches)
+(test-basic-match (determinize lang3-nfa) lang3-string-matches)
View
93 test/swangee/core_test.clj
@@ -2,93 +2,34 @@
(:use clojure.test)
(:require [swangee.core :as swangee]))
-;; For these tests, we use the simple language defined by the
-;; regular expression "ab(bb|c)*".
-
-(def test-nfa (swangee/nfa :states [:1 :2 :3]
- :transitions [{:1 {\a :2}
- :2 {\b #{:3}}
- :3 {\c :3
- \b #{:2}}}]
- :initial-state #{:1}
- :accepting-states #{:3}))
-
-(deftest simple-step-nfa
- ;; Start at initial configuration and step once.
- (is (= (swangee/config #{:2} (seq "bccb"))
- (swangee/step test-nfa (swangee/config (:initial-state test-nfa)
- "abccb"))))
- ;; Try another step.
- (is (= (swangee/config #{:3} (seq "ccb"))
- (swangee/step test-nfa (swangee/config #{:2}
- "bccb"))))
-
- ;; Undefined input.
- (is (= (swangee/config #{} (seq "ddd"))
- (swangee/step test-nfa (swangee/config #{:1} "dddd")))))
-
-;; Define the same FA as above, as a DFA.
-(def test-dfa (swangee/dfa :states {:1 (swangee/compiled-state {\a :2} false)
- :2 (swangee/compiled-state {\b :3} false)
- :3 (swangee/compiled-state {\c :3
- \b :2} true)}
- :initial-state :1))
-
-(deftest simple-step-dfa
- ;; Start at initial configuration and step once.
- (is (= (swangee/config :2 (seq "bccb"))
- (swangee/step test-dfa (swangee/config (:initial-state test-dfa)
- "abccb"))))
-
- ;; Try another step.
- (is (= (swangee/config :3 (seq "ccb"))
- (swangee/step test-dfa (swangee/config :2 "bccb"))))
-
- ;; Undefined input.
- (is (= (swangee/config nil (seq "ddd"))
- (swangee/step test-dfa (swangee/config :1 "dddd")))))
;;
-;; Core operations (FA-independent)
+;; Core operations (FA-independent, actual tests in nfa/dfa tests)
;;
+;; For these tests, we use the simple language defined by the
+;; regular expression "ab(bb|c)*".
(defmacro test-basic-run
- [fa]
+ [fa accepted-strings rejected-strings]
(let [test-name (gensym "basic-run")]
`(deftest ~test-name
- ;; Basic run of entire string expecting success
- (is (= true
- (swangee/run ~fa "abccbb")))
+ ;; Basic run of entire string expecting success.
+ (doseq [s# ~accepted-strings]
+ (is (= true
+ (swangee/run ~fa s#))))
- ;; Basic run of entire string with characters not in any transition.
- (is (= false
- (swangee/run ~fa "abddcba"))))))
-
-(test-basic-run test-nfa)
-(test-basic-run test-dfa)
+ ;; Basic run of entire string that is not in the language.
+ (doseq [s# ~rejected-strings]
+ (is (= false
+ (swangee/run ~fa s#)))))))
(defmacro test-basic-match
- [fa]
+ [fa string-matches] ;; string-matches seq of pairs of strings and matches.
(let [test-name (gensym "basic-match")]
`(deftest ~test-name
- ;; Basic match of string prefix expecting success
- (is (= (seq "abc")
- (swangee/match ~fa "abcd")))
-
- ;; Basic match of string prefix expecting failure
- (is (= []
- (swangee/match ~fa "dbbabc")))
-
- ;; Basic match of string prefix consuming entire string
- (is (= (seq "abccbb"))
- (swangee/match ~fa "abccbb"))
-
- ;; Basic match of string with multiple matches
- (is (= (seq "abccbbc"))
- (swangee/match ~fa "abccbbc")))))
-
-(test-basic-match test-nfa)
-(test-basic-match test-dfa)
+ (doseq [[string# match#] ~string-matches]
+ (is (= match#
+ (swangee/match ~fa string#)))))))
(defmacro test-complement
[fa]
@@ -106,8 +47,6 @@
(swangee/run (swangee/complement (swangee/complement ~fa))
"abccbb"))))))
-(test-complement test-nfa)
-
View
30 test/swangee/dfa_test.clj
@@ -0,0 +1,30 @@
+(ns swangee.dfa-test
+ (:use clojure.test
+ [swangee core-test test-automata-defs dfa])
+ (:require [swangee.core :as swangee]))
+
+(deftest simple-step-dfa
+ ;; Start at initial configuration and step once.
+ (is (= (swangee/config :2 (seq "bccb"))
+ (swangee/step lang1-dfa (swangee/config (:initial-state lang1-dfa)
+ "abccb"))))
+
+ ;; Try another step.
+ (is (= (swangee/config :3 (seq "ccb"))
+ (swangee/step lang1-dfa (swangee/config :2 "bccb"))))
+
+ ;; Undefined input.
+ (is (= (swangee/config nil (seq "ddd"))
+ (swangee/step lang1-dfa (swangee/config :1 "dddd")))))
+
+
+;;
+;; Core operations tests.
+;;
+(test-basic-run lang1-dfa lang1-strings not-lang1-strings)
+(test-basic-run lang2-dfa lang2-strings not-lang2-strings)
+(test-basic-run lang3-dfa lang3-strings not-lang3-strings)
+
+(test-basic-match lang1-dfa lang1-string-matches)
+(test-basic-match lang2-dfa lang2-string-matches)
+(test-basic-match lang3-dfa lang3-string-matches)
View
136 test/swangee/nfa_test.clj
@@ -0,0 +1,136 @@
+(ns swangee.nfa-test
+ (:use clojure.test
+ [swangee core-test test-automata-defs nfa])
+ (:require [swangee.core :as swangee]))
+
+;;
+;; Data definitions
+;;
+
+(def transitions-with-eps {:a {\b :b
+ nil :b}
+ :b {\d :d
+ \c :c
+ nil #{:c}}
+ :c {}
+ :d {nil #{:b :c}}})
+
+;; Test the espilon-closure function.
+
+(deftest epsilon-closure-test
+ ;; Single states.
+ (is (= #{:a :b :c}
+ (epsilon-closure transitions-with-eps :a)))
+ (is (= #{:b :c}
+ (epsilon-closure transitions-with-eps :b)))
+ (is (= #{:c}
+ (epsilon-closure transitions-with-eps :c)))
+ (is (= #{:b :c :d}
+ (epsilon-closure transitions-with-eps :d)))
+ ;; Single states as sets.
+ (is (= #{:a :b :c}
+ (epsilon-closure transitions-with-eps #{:a})))
+ (is (= #{:b :c}
+ (epsilon-closure transitions-with-eps #{:b})))
+ (is (= #{:c}
+ (epsilon-closure transitions-with-eps #{:c})))
+ (is (= #{:b :c :d}
+ (epsilon-closure transitions-with-eps #{:d})))
+ ;; Sets of states
+ (is (= #{:a :b :c}
+ (epsilon-closure transitions-with-eps #{:a :b})))
+ (is (= #{:b :c}
+ (epsilon-closure transitions-with-eps #{:b :c})))
+ (is (= #{:b :c :d}
+ (epsilon-closure transitions-with-eps #{:d})))
+ (is (= #{:a :b :c :d}
+ (epsilon-closure transitions-with-eps #{:a :b :c :d}))))
+
+(deftest epsilon-closure-nfas
+ ;; lang1-nfa
+ (is (= #{:1} (epsilon-closure (:transitions lang1-nfa) :1)))
+ (is (= #{:2} (epsilon-closure (:transitions lang1-nfa) :2)))
+ (is (= #{:3} (epsilon-closure (:transitions lang1-nfa) :3)))
+ ;; lang2-nfa
+ (is (= #{:q0 :q1 :q2} (epsilon-closure (:transitions lang2-nfa) :q0)))
+ (is (= #{:q1 :q2} (epsilon-closure (:transitions lang2-nfa) :q1)))
+ (is (= #{:q2} (epsilon-closure (:transitions lang2-nfa) :q2)))
+ ;; lang3-nfa
+ (is (= #{:1 :2 :4} (epsilon-closure (:transitions lang3-nfa) :1)))
+ (is (= #{:2} (epsilon-closure (:transitions lang3-nfa) :2)))
+ (is (= #{:3 :6} (epsilon-closure (:transitions lang3-nfa) :3)))
+ (is (= #{:4} (epsilon-closure (:transitions lang3-nfa) :4)))
+ (is (= #{:5 :6} (epsilon-closure (:transitions lang3-nfa) :5)))
+ (is (= #{:6} (epsilon-closure (:transitions lang3-nfa) :6)))
+ (is (= #{:1 :2 :4} (epsilon-closure (:transitions lang3-nfa) #{:1}))))
+
+;; See core_test.clj for the language being tested.
+
+(deftest simple-step-nfa
+ ;; Start at initial configuration and step once.
+ (is (= (swangee/config #{:2} (seq "bccb"))
+ (swangee/step lang1-nfa (swangee/config (:initial-state lang1-nfa)
+ "abccb"))))
+ ;; Try another step.
+ (is (= (swangee/config #{:3} (seq "ccb"))
+ (swangee/step lang1-nfa (swangee/config #{:2}
+ "bccb"))))
+
+ ;; Undefined input.
+ (is (= (swangee/config #{} (seq "ddd"))
+ (swangee/step lang1-nfa (swangee/config #{:1} "dddd")))))
+
+;; Run the core operations tests on this nfa.
+(test-basic-run lang1-nfa lang1-strings not-lang1-strings)
+(test-basic-run lang2-nfa lang2-strings not-lang2-strings)
+(test-basic-run lang3-nfa lang3-strings not-lang3-strings)
+
+(test-basic-match lang1-nfa lang1-string-matches)
+(test-basic-match lang2-nfa lang2-string-matches)
+(test-basic-match lang3-nfa lang3-string-matches)
+
+(test-complement lang1-nfa)
+
+;;
+;; Test an NFA with epsilon-transitions on the language a*b*c*.
+;;
+
+(deftest simple-step-e-nfa
+ ;; Start at initial configuration and step once.
+ (is (= (swangee/config #{:q0} (seq "bc"))
+ (swangee/step lang2-nfa (swangee/config (:initial-state lang2-nfa)
+ "abc"))))
+ (is (= (swangee/config #{:q1} (seq "c"))
+ (swangee/step lang2-nfa (swangee/config #{:q1}
+ "bc"))))
+ (is (= (swangee/config #{:q2} '())
+ (swangee/step lang2-nfa (swangee/config #{:q2}
+ "c")))))
+
+;;
+;; Test NFA-specific operations
+;;
+
+(deftest simple-move-nfa
+ (is (= #{:2}
+ (move-nfa lang1-nfa #{:1} \a)))
+ (is (= #{}
+ (move-nfa lang1-nfa #{:1} \b)))
+ (is (= #{:q0}
+ (move-nfa lang2-nfa #{:q0} \a)))
+ (is (= #{:q1}
+ (move-nfa lang2-nfa #{:q0} \b)))
+ (is (= #{:2 :5}
+ (move-nfa lang3-nfa #{:1} \b)))
+ (is (= #{:3 :4}
+ (move-nfa lang3-nfa #{:1} \a))))
+
+(deftest simple-outgoing-symbols
+ (is (= #{\a}
+ (outgoing-symbols lang1-nfa #{:1})))
+ (is (= #{\b \c}
+ (outgoing-symbols lang1-nfa #{:3})))
+ (is (= #{\a}
+ (outgoing-symbols lang2-nfa #{:q0})))
+ (is (= #{}
+ (outgoing-symbols lang3-nfa #{:6}))))
View
102 test/swangee/test_automata_defs.clj
@@ -0,0 +1,102 @@
+(ns swangee.test-automata-defs
+ "Definitions of automata for use in other tests."
+ (:use [swangee nfa dfa]))
+
+;;
+;; Language 1
+;;
+;; The language ab(bb|c)*. NFA has no epsilon transitions.
+(def lang1-nfa (nfa :states [:1 :2 :3]
+ :transitions {:1 {\a :2}
+ :2 {\b #{:3}}
+ :3 {\c :3
+ \b #{:2}}}
+ :initial-state #{:1}
+ :accepting-states #{:3}))
+
+(def lang1-dfa (dfa :states {:1 (compiled-state {\a :2} false)
+ :2 (compiled-state {\b :3} false)
+ :3 (compiled-state {\c :3
+ \b :2} true)}
+ :initial-state :1))
+
+(def lang1-strings ["abccbb" "ab" "abc" "abbb" "abbbccc" "abccbb"])
+(def not-lang1-strings ["" "a" "b" "aba" "abac" "abbc" "abbbb" "abbcb"
+ "abbbbccc" "abddcba" "dfa"])
+(def lang1-string-matches [["" []]
+ ["adbc" []]
+ ["abcd" (seq "abc")]
+ ["dbbabc" []]
+ ["ab" (seq "ab")]
+ ["abccbb" (seq "abccbb")]
+ ["abccbbc" (seq "abccbbc")]])
+
+;;
+;; Language 2
+;;
+;; The language a*b*c*.
+(def lang2-nfa (nfa :states [:q0 :q1 :q2]
+ :transitions {:q0 {\a :q0
+ nil :q1}
+ :q1 {\b :q1
+ nil :q2}
+ :q2 {\c :q2}}
+ :initial-state #{:q0}
+ :accepting-states #{:q2}))
+
+(def lang2-dfa (dfa :states {:q0 (compiled-state {\a :q0
+ \b :q1
+ \c :q2} true)
+ :q1 (compiled-state {\b :q1
+ \c :q2} true)
+ :q2 (compiled-state {\c :q2} true)}
+ :initial-state :q0))
+
+(def lang2-strings ["" "a" "b" "c" "aa" "bb" "cc" "abc" "aabbc" "aabbcc"])
+(def not-lang2-strings ["aba" "abac" "dfa" "cccb"])
+(def lang2-string-matches [["" []]
+ ["a" (seq "a")]
+ ["abbd" (seq "abb")]
+ ["abc" (seq "abc")]
+ ["babc" (seq "b")]
+ ["dfa" []]
+ ["cccp" (seq "ccc")]])
+
+;;
+;; Language 3
+;;
+;; The language (b*a)|(a*b).
+(def lang3-nfa (nfa :states [:1 :2 :3 :4 :5 :6]
+ :transitions {:1 {nil #{:2 :4}}
+ :2 {\b :2
+ \a :3}
+ :3 {nil :6}
+ :4 {\a :4
+ \b :5}
+ :5 {nil :6}
+ :6 {}}
+ :initial-state #{:1}
+ :accepting-states #{:6}))
+
+(def lang3-dfa (dfa :states {:1 (compiled-state {\a :2
+ \b :3} false)
+ :2 (compiled-state {\a :4
+ \b :6} true)
+ :3 (compiled-state {\a :6
+ \b :5} true)
+ :4 (compiled-state {\a :4
+ \b :6} false)
+ :5 (compiled-state {\a :6
+ \b :5} false)
+ :6 (compiled-state {} true)}
+ :initial-state :1))
+
+(def lang3-strings ["a" "b" "ba" "ab" "bbba" "aaaab"])
+(def not-lang3-strings ["aa" "bb" "baa" "bab" "aaabb" "aba" "dfa"])
+(def lang3-string-matches [["" []]
+ ["a" (seq "a")]
+ ["aa" (seq "a")]
+ ["bb" (seq "b")]
+ ["baa" (seq "ba")]
+ ["aaabb" (seq "aaab")]
+ ["dfa" []]])

No commit comments for this range

Something went wrong with that request. Please try again.