PFP Homework 1 - Revision history

Beh01 at 13:03, 10 October 2023

2023-10-10T13:03:27Z

Beh01 at 12:51, 10 October 2023

2023-10-10T12:51:02Z

Beh01 at 12:44, 10 October 2023

2023-10-10T12:44:39Z

Beh01 at 12:42, 10 October 2023

2023-10-10T12:42:58Z

Beh01 at 12:38, 10 October 2023

2023-10-10T12:38:55Z

Beh01 at 12:29, 10 October 2023

2023-10-10T12:29:50Z

Beh01 at 12:16, 10 October 2023

2023-10-10T12:16:11Z

Beh01 at 12:12, 10 October 2023

2023-10-10T12:12:00Z

Beh01 at 12:10, 10 October 2023

2023-10-10T12:10:49Z

Beh01 at 12:07, 10 October 2023

2023-10-10T12:07:37Z

@@ Line 31: / Line 31: @@
 True
 ghci>isDeterministic ex2
-True
+False
 </syntaxhighlight>

@@ Line 41: / Line 41: @@
 ghci>isAccepting ex2 "aaa"
 False
 </syntaxhighlight>

@@ Line 34: / Line 34: @@
 </syntaxhighlight>
-* Second function runs automaton for given string and establishes, if given input string is accepted by the given automaton. It should work for both deterministic and non-deteministic finite automatons.
+* Second function runs automaton for given string and establishes, if given input string is accepted by the given automaton. It should work for both deterministic and non-deterministic finite automatons.
 <syntaxhighlight lang="Haskell">isAccepting:: Automaton -> String -> Bool</syntaxhighlight>
 <syntaxhighlight lang="Haskell" class="myDark">

@@ Line 30: / Line 30: @@
 ghci>isDeterministic ex1
 True
 </syntaxhighlight>

@@ Line 17: / Line 17: @@
 <syntaxhighlight lang="Haskell">
 ex1 :: Automaton
-ex1 = (3, [0], [2], "ab", [(0,'a',1), (0,'b',0), (1,'a',1), (1,'b',2), (2,'a',1), (2,'b',0)])
+ex1 = (3, "ab", [(0,'a',1), (0,'b',0), (1,'a',1), (1,'b',2), (2,'a',1), (2,'b',0)], 0, [2],)
 ex2 :: Automaton
-ex2 = (3, [0], [2], "ab", [(0,'a',1), (0,'a',0), (0,'b',0), (1,'b',2)])
+ex2 = (3, "ab", [(0,'a',1), (0,'a',0), (0,'b',0), (1,'b',2)], 0, [2])
 </syntaxhighlight>
-* Create a function, that sorts an array using quicksort algorithm [https://en.wikipedia.org/wiki/Quicksort <code>quicksort</code>]. Inside, you must use the mutable array [https://hackage.haskell.org/package/array-0.5.4.0/docs/Data-Array-ST.html#t:STArray <code>STArray</code>].
+Your task will be to create three functions:
-<syntaxhighlight lang="Haskell">quickSort :: Array Int Int -> Array Int Int</syntaxhighlight>
 <syntaxhighlight lang="Haskell" class="myDark">
-ghci> elems $ quickSort $  listArray (0,5) [8,4,9,6,7,1]
+ghci>isDeterministic ex1
-[1,4,6,7,8,9]
+True
 </syntaxhighlight>

@@ Line 1: / Line 1: @@
 = Automatons =
-Usually, a finite automaton defined as: <math>(Q, \Sigma, \delta, q_0, F)</math> where Q represents a states, next is input alphabet, then transitions (<math>Q \times \Sigma \rightarrow Q</math>), <math>q_0</math> is starting state and finaly there is a set of final states.
+Usually, a finite automaton defined as: <math>(Q, \Sigma, \delta, q_0, F)</math> where Q represents states, next is input alphabet, then transitions (<math>Q \times \Sigma \rightarrow Q</math>), <math>q_0</math> is starting state and finally there is a set of final states.
-In our case, an finite automaton is represented by types:
+In our case, a finite automaton is represented by types:
 <syntaxhighlight lang="Haskell">
 type Transition = (Int, Char, Int)
@@ Line 9: / Line 9: @@
 where:
 * first number <code>N</code> defines number of states - states will be coded by integer numbers in interval <math><0, N)</math>;
-* second element is a string containing the input symbols - you can safely assume, it contains no duplicities;
+* second element is a string containing the input symbols - you can safely assume; it contains no duplicities;
 * third is a list defining the trasition function - elementary transition is a triple <code>(q1, a, q2)</code> representing a transition: <math>q_1 \times a \rightarrow q_2</math>;
 * <math>q_0</math> is a number from interval <math><0, N)</math>;
-* finally, there is a list of number representing posible states that are final in defined automaton.
+* finally, there is a list of number representing possible states that are final in defined automaton.
 As examples we can use following automatons: