Binary file cws/cw05.pdf has changed
--- a/cws/cw05.tex Fri Mar 10 06:22:30 2017 +0000
+++ b/cws/cw05.tex Fri Mar 10 23:01:17 2017 +0000
@@ -8,7 +8,7 @@
\section*{Replacement Coursework 2 (Automata)}
This coursework is worth 10\%. It is about deterministic and
-non-deterministic finite automata. The coursework is due on ??? March
+non-deterministic finite automata. The coursework is due on 21 March
at 5pm. Make sure the files you submit can be processed by just
calling \texttt{scala <<filename.scala>>}.\bigskip
@@ -36,8 +36,8 @@
\noindent
There are many uses for Deterministic Finite Automata (DFAs), for
example for testing whether a string matches a pattern or not. DFAs
-consist of some states (circles) and transitions (edges) between
-states. For example consider the DFA
+consist of some states (circles) and some transitions (edges) between
+states. For example the DFA
\begin{center}
\begin{tikzpicture}[scale=1.5,>=stealth',very thick,auto,
@@ -59,13 +59,13 @@
\noindent
has three states ($Q_0$, $Q_1$ and $Q_2$), whereby $Q_0$ is the
starting state of the DFA and $Q_2$ is the accepting state. The latter
-indicated by double lines. In general, a DFA can have any number of
+is indicated by double lines. In general, a DFA can have any number of
accepting states, but only a single starting state.
Transitions are edges between states labelled with a character. The
idea is that if we are in state $Q_0$, say, and get an $a$, we can go
to state $Q_1$. If we are in state $Q_2$ and get an $a$, we can stay
-in state $Q_2$; if we get a $b$ in $Q_2$, then we have to go to state
+in state $Q_2$; if we get a $b$ in $Q_2$, then can go to state
$Q_0$. The main point of DFAs is that if we are in a state and get a
character, it is always clear which is the next state---there can only
be at most one. The task of Part 1 is to implement such DFAs in Scala
@@ -109,14 +109,14 @@
method \texttt{isDefinedAt} that can be used to check whether an
input produces a result or not. For example
- \begin{lstlisting}[language=Scala,numbers=none]
+\begin{lstlisting}[language=Scala,numbers=none]
dfa_trans.isDefinedAt((Q0, 'a'))
dfa_trans.isDefinedAt((Q0, 'c'))
- \end{lstlisting}
+\end{lstlisting}
\noindent
gives \texttt{true} in the first case and \texttt{false} in the
- second. There is also a method \texttt{lift} that transformes a
+ second. There is also a method \texttt{lift} that transforms a
partial function into a ``normal'' function returning an optional
value: if the partial function is defined on the input, the lifted
function will return \texttt{Some}; if it is not defined, then
@@ -136,7 +136,7 @@
state $Q_1$ (as option since there might not be such a state in general).\\
\mbox{}\hfill\mbox{[1 Mark]}
-\item[(4)] DFAs are defined as a triple: (staring state, transitions,
+\item[(4)] DFAs are defined as a triple: (starting state, transitions,
set of accepting states). Write a function \texttt{accepts} that tests whether
a string is accepted by an DFA or not. For this start in the
starting state of the DFA, use the function under (3) to calculate
@@ -196,7 +196,7 @@
\end{lstlisting}
\noindent
-The point is that the 3rd element in this set states that in $R_2$ and
+The point is that the 3rd element in this set makes sure that in state $R_2$ and
given an $a$, we can go to state $R_1$; and the 4th element, in $R_2$,
given an $a$, we can also go to state $R_3$. When following
transitions from a state, we have to look at all partial functions in
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/progs/automata.scala Fri Mar 10 23:01:17 2017 +0000
@@ -0,0 +1,197 @@
+// NFAs and DFAs based on Scala's partial functions
+
+
+// (1) Write a polymorphic function that tests whether the
+// intersection of two sets is non-empty
+
+def share[A](a: Set[A], b: Set[A]) : Boolean = ...
+
+
+share(Set(1,2,3), Set(2, 3, 4)) // true
+share(Set(1,2,3), Set(4, 5, 6)) // false
+
+
+// State nodes of the DFAs and NFAs
+abstract class State
+type States = Set[State]
+
+// Some states for test cases
+case object Q0 extends State
+case object Q1 extends State
+case object Q2 extends State
+case object Q3 extends State
+case object Q4 extends State
+case object Q5 extends State
+case object Q6 extends State
+
+
+// Transitions for DFAs and NFAs
+type Trans = PartialFunction[(State, Char), State]
+type NTrans = Set[Trans]
+
+
+// example transition of an DFA
+val dtrans : Trans =
+ { case (Q0, 'a') => Q1
+ case (Q0, 'b') => Q0
+ case (Q1, 'a') => Q2
+ case (Q1, 'b') => Q0
+ case (Q2, 'a') => Q2
+ case (Q2, 'b') => Q0
+ }
+
+
+// (2) Write a function that takes a transition and a
+// (state, character)-pair as arguments and produces an
+// optional state (the state specified by the partial transition
+// function whenever it is defined; if the transition function
+// is undefined, return None.
+
+def fire(e: Trans, qc: (State, Char)) : Option[State] = ...
+
+
+// (3) Write a function that takes a transition, a state
+// and a list of characters as arguments and produces
+// the state generated by following the transitions for
+// each character in the list.
+
+def nexts(trans: Trans, q: State, s: List[Char]) : Option[State] = ...
+
+
+
+// class for DFAs
+case class DFA(start: State, // starting state
+ trans: Trans, // transition
+ fins: States) // final states
+
+// (4) Write a function that tests whether a string is accepted
+// by an DFA or not.
+
+def accepts(dfa: DFA, s: String) : Boolean = ...
+
+
+
+// DFA examples
+
+val dtrans1 : Trans =
+ { case (Q0, 'a') => Q0
+ case (Q0, 'b') => Q1
+ }
+
+val dfa1 = DFA(Q0, dtrans1, Set[State](Q1))
+
+accepts(dfa1, "aaab") // true
+accepts(dfa1, "aacb") // false
+
+
+// NFAs
+
+
+// (5) Write a function that takes a transition set, a state
+// and a character as arguments, and calculates all possible
+// next states (returned as set).
+
+def nnext(trans: NTrans, q: State, c: Char) : States = ...
+
+
+// (6) Write a function that takes a transition set, a set of states
+// and a character as arguments, and calculates all possible
+// next states that can be reached from any state in the set.
+
+def nnexts(trans: NTrans, qs: States, c: Char) : States = ...
+
+
+
+// (7) Write a function that lifts nnexts from from single
+// characters to lists of characters.
+def nnextss(trans: NTrans, qs: States, s: List[Char]) : States = ...
+
+
+// class for NFAs
+case class NFA(start: States, // starting state
+ trans: NTrans, // transition edges
+ fins: States) // final states
+
+
+// (8) Write a function that tests whether a string is
+// accepted by an NFA or not.
+
+def naccepts(nfa: NFA, s: String) : Boolean = ...
+
+
+// (9) Write similar functions as in (7) and (8), but instead of
+// returning states or a boolean, calculate the number of states
+// that need to be followed in each step.
+
+def max_nextss(trans: NTrans, qs: States, s: List[Char], max: Int) : Int = ...
+
+def max_accepts(nfa: NFA, s: String) : Int = ...
+
+
+// NFA examples
+
+
+// 1
+val trans1 : NTrans = Set(
+ { case (Q0, 'a') => Q1 },
+ { case (Q0, _) => Q0 },
+ { case (Q1, _) => Q2 },
+ { case (Q2, _) => Q3 },
+ { case (Q3, _) => Q4 },
+ { case (Q4, 'b') => Q5 },
+ { case (Q5, 'c') => Q6 }
+)
+
+val nfa1 = NFA(Set[State](Q0), trans1, Set[State](Q6))
+
+naccepts(nfa1, "axaybzbc") // true
+naccepts(nfa1, "aaaaxaybzbc") // true
+naccepts(nfa1, "axaybzbd") // false
+
+// the nfa has five states, which might be all
+// active
+
+max_accepts(nfa1, "axaybzbc") // 3
+max_accepts(nfa1, "aaaaxaybzbc") // 5
+max_accepts(nfa1, "axaybzbd") // 3
+max_accepts(nfa1, "aaaaaaaaaaaaaxaybzbd") // 5
+
+
+// 2
+val trans2 : NTrans = Set(
+ { case (Q0, 'a') => Q0 },
+ { case (Q0, 'a') => Q1 },
+ { case (Q0, 'b') => Q2 },
+ { case (Q1, 'a') => Q1 },
+ { case (Q2, 'b') => Q2 }
+)
+
+val nfa2 = NFA(Set[State](Q0), trans2, Set[State](Q2))
+
+naccepts(nfa2, "aa") // false
+naccepts(nfa2, "aaaaa") // false
+naccepts(nfa2, "aaaaab") // true
+naccepts(nfa2, "aaaaabbb") // true
+naccepts(nfa2, "aaaaabbbaaa") // false
+naccepts(nfa2, "ac") // false
+
+// 3
+val trans3 : NTrans = Set(
+ { case (Q0, _) => Q0 },
+ { case (Q0, 'a') => Q1 },
+ { case (Q0, 'b') => Q3 },
+ { case (Q1, 'b') => Q2 },
+ { case (Q2, 'c') => Q5 },
+ { case (Q3, 'c') => Q4 },
+ { case (Q4, 'd') => Q5 }
+)
+
+val nfa3 = NFA(Set[State](Q0), trans3, Set[State](Q5))
+
+naccepts(nfa3, "aaaaabc") // true
+naccepts(nfa3, "aaaabcd") // true
+naccepts(nfa3, "aaaaab") // false
+naccepts(nfa3, "aaaabc") // true
+naccepts(nfa3, "aaaaabbbaaa") // false
+
+
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/progs/automata_sol.scala Fri Mar 10 23:01:17 2017 +0000
@@ -0,0 +1,222 @@
+// NFAs and DFAs based on Scala's partial functions
+
+
+// (1) Write a polymorphic function that tests whether the
+// intersection of two sets is non-empty
+
+def share[A](a: Set[A], b: Set[A]) : Boolean =
+ !(a intersect b).isEmpty
+
+share(Set(1,2,3), Set(2, 3, 4)) // true
+share(Set(1,2,3), Set(4, 5, 6)) // false
+
+
+// State nodes of the DFAs and NFAs
+abstract class State
+type States = Set[State]
+
+// Some states for test cases
+case object Q0 extends State
+case object Q1 extends State
+case object Q2 extends State
+case object Q3 extends State
+case object Q4 extends State
+case object Q5 extends State
+case object Q6 extends State
+
+
+// Transitions for DFAs and NFAs
+type Trans = PartialFunction[(State, Char), State]
+type NTrans = Set[Trans]
+
+
+// example transition of an DFA
+val dtrans : Trans =
+ { case (Q0, 'a') => Q1
+ case (Q0, 'b') => Q0
+ case (Q1, 'a') => Q2
+ case (Q1, 'b') => Q0
+ case (Q2, 'a') => Q2
+ case (Q2, 'b') => Q0
+ }
+
+
+// (2) Write a function that takes a transition and a
+// (state, character)-pair as arguments and produces an
+// optional state (the state specified by the partial transition
+// function whenever it is defined; if the transition function
+// is undefined, return None.
+
+def fire(e: Trans, qc: (State, Char)) : Option[State] =
+ e.lift.apply(qc)
+
+
+// (3) Write a function that takes a transition, a state
+// and a list of characters as arguments and produces
+// the state generated by following the transitions for
+// each character in the list.
+
+def nexts(trans: Trans, q: State, s: List[Char]) : Option[State] = s match {
+ case Nil => Some(q)
+ case c::cs => fire(trans, (q, c)).flatMap(nexts(trans, _, cs))
+}
+
+
+
+// class for DFAs
+case class DFA(start: State, // starting state
+ trans: Trans, // transition
+ fins: States) // final states
+
+// (4) Write a function that tests whether a string is accepted
+// by an DFA or not.
+
+def accepts(dfa: DFA, s: String) : Boolean = nexts(dfa.trans, dfa.start, s.toList) match {
+ case None => false
+ case Some(q) => dfa.fins contains q
+}
+
+
+// DFA examples
+
+val dtrans1 : Trans =
+ { case (Q0, 'a') => Q0
+ case (Q0, 'b') => Q1
+ }
+
+val dfa1 = DFA(Q0, dtrans1, Set[State](Q1))
+
+accepts(dfa1, "aaab") // true
+accepts(dfa1, "aacb") // false
+
+
+// NFAs
+
+
+// (5) Write a function that takes a transition set, a state
+// and a character as arguments, and calculates all possible
+// next states (returned as set).
+
+def nnext(trans: NTrans, q: State, c: Char) : States = {
+ trans.map(fire(_, (q, c))).flatten
+}
+
+// (6) Write a function that takes a transition set, a set of states
+// and a character as arguments, and calculates all possible
+// next states that can be reached from any state in the set.
+
+def nnexts(trans: NTrans, qs: States, c: Char) : States = {
+ qs.flatMap(nnext(trans, _, c))
+}
+
+
+// (7) Write a function that lifts nnexts from from single
+// characters to lists of characters.
+def nnextss(trans: NTrans, qs: States, s: List[Char]) : States = s match {
+ case Nil => qs
+ case c::cs => {
+ val ns = nnexts(trans, qs, c)
+ nnextss(trans, ns, cs)
+ }
+}
+
+// class for NFAs
+case class NFA(start: States, // starting state
+ trans: NTrans, // transition edges
+ fins: States) // final states
+
+
+// (8) Write a function that tests whether a string is
+// accepted by an NFA or not.
+
+def naccepts(nfa: NFA, s: String) : Boolean = {
+ share(nnextss(nfa.trans, nfa.start, s.toList), nfa.fins)
+}
+
+
+// (9) Write similar functions as in (7) and (8), but instead of
+// returning states or a boolean, calculate the number of states
+// that need to be followed in each step.
+
+def max_nextss(trans: NTrans, qs: States, s: List[Char], max: Int) : Int = s match {
+ case Nil => max
+ case c::cs => {
+ val ns = nnexts(trans, qs, c)
+ val ns_size = ns.size
+ if (max < ns_size) max_nextss(trans, ns, cs, ns_size)
+ else max_nextss(trans, ns, cs, max)
+ }
+}
+
+def max_accepts(nfa: NFA, s: String) : Int = {
+ max_nextss(nfa.trans, nfa.start, s.toList, 0)
+}
+
+
+// NFA examples
+
+
+// 1
+val trans1 : NTrans = Set(
+ { case (Q0, 'a') => Q1 },
+ { case (Q0, _) => Q0 },
+ { case (Q1, _) => Q2 },
+ { case (Q2, _) => Q3 },
+ { case (Q3, _) => Q4 },
+ { case (Q4, 'b') => Q5 },
+ { case (Q5, 'c') => Q6 }
+)
+
+val nfa1 = NFA(Set[State](Q0), trans1, Set[State](Q6))
+
+naccepts(nfa1, "axaybzbc") // true
+naccepts(nfa1, "aaaaxaybzbc") // true
+naccepts(nfa1, "axaybzbd") // false
+
+// the nfa has five states, which might be all
+// active
+
+max_accepts(nfa1, "axaybzbc") // 3
+max_accepts(nfa1, "aaaaxaybzbc") // 5
+max_accepts(nfa1, "axaybzbd") // 3
+max_accepts(nfa1, "aaaaaaaaaaaaaxaybzbd") // 5
+
+
+// 2
+val trans2 : NTrans = Set(
+ { case (Q0, 'a') => Q0 },
+ { case (Q0, 'a') => Q1 },
+ { case (Q0, 'b') => Q2 },
+ { case (Q1, 'a') => Q1 },
+ { case (Q2, 'b') => Q2 }
+)
+
+val nfa2 = NFA(Set[State](Q0), trans2, Set[State](Q2))
+
+naccepts(nfa2, "aa") // false
+naccepts(nfa2, "aaaaa") // false
+naccepts(nfa2, "aaaaab") // true
+naccepts(nfa2, "aaaaabbb") // true
+naccepts(nfa2, "aaaaabbbaaa") // false
+naccepts(nfa2, "ac") // false
+
+// 3
+val trans3 : NTrans = Set(
+ { case (Q0, _) => Q0 },
+ { case (Q0, 'a') => Q1 },
+ { case (Q0, 'b') => Q3 },
+ { case (Q1, 'b') => Q2 },
+ { case (Q2, 'c') => Q5 },
+ { case (Q3, 'c') => Q4 },
+ { case (Q4, 'd') => Q5 }
+)
+
+val nfa3 = NFA(Set[State](Q0), trans3, Set[State](Q5))
+
+naccepts(nfa3, "aaaaabc") // true
+naccepts(nfa3, "aaaabcd") // true
+naccepts(nfa3, "aaaaab") // false
+naccepts(nfa3, "aaaabc") // true
+naccepts(nfa3, "aaaaabbbaaa") // false
+
+