# HG changeset patch # User Christian Urban # Date 1489186877 0 # Node ID 4fc05d4f0e018534cbb4c20cb4a5b191109ad89c # Parent 564b4baec85e8c088d7dba55847afba67eaa763d updated diff -r 564b4baec85e -r 4fc05d4f0e01 cws/cw05.pdf Binary file cws/cw05.pdf has changed diff -r 564b4baec85e -r 4fc05d4f0e01 cws/cw05.tex --- 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 <>}.\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 diff -r 564b4baec85e -r 4fc05d4f0e01 progs/automata.scala --- /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 + + diff -r 564b4baec85e -r 4fc05d4f0e01 progs/automata_sol.scala --- /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 + +