Difference between revisions of "PFP Homework 1"

From Marek Běhálek Wiki
Jump to navigation Jump to search
 
(14 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
= Automatons =  
 
= Automatons =  
−
Let say, we have a finite automaton defined as: <math>(Q, &Sigma; , q_0, F, )</math>  
+
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, a finite automaton is represented by types:
 
<syntaxhighlight lang="Haskell">
 
<syntaxhighlight lang="Haskell">
 
type Transition = (Int, Char, Int)
 
type Transition = (Int, Char, Int)
−
type Automaton = (Int, String, [Int], Int, [Transition ])
+
type Automaton = (Int, String, [Transition], Int, [Int])
 
</syntaxhighlight>
 
</syntaxhighlight>
 +
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;
 +
* 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 possible states that are final in defined automaton.
  
−
where states are coded with numbers from 0 to n
+
As examples we can use following automatons:
−
 
 
 
<syntaxhighlight lang="Haskell">
 
<syntaxhighlight lang="Haskell">
 
ex1 :: Automaton  
 
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 :: 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>
 +
 
 +
Your task will be to create three functions:
 +
 
 +
* First function checks if a given finite automaton is a '''deterministic''' finite automaton.
 +
<syntaxhighlight lang="Haskell">isDeterministic:: Automaton  -> Bool</syntaxhighlight>
 +
<syntaxhighlight lang="Haskell" class="myDark">
 +
ghci>isDeterministic ex1
 +
True
 +
ghci>isDeterministic ex2
 +
False
 +
</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-deterministic finite automatons.
 +
<syntaxhighlight lang="Haskell">isAccepting:: Automaton -> String -> Bool</syntaxhighlight>
 +
<syntaxhighlight lang="Haskell" class="myDark">
 +
ghci>isAccepting ex1 "aab"
 +
True
 +
ghci>isAccepting ex2 "aaa"
 +
False
 
</syntaxhighlight>
 
</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>].
+
* Finally, create a function that takes a non-deterministic automaton and produces it's deterministic equivalent (the output can be very '''different''' based on used methodology).  
−
<syntaxhighlight lang="Haskell">quickSort :: Array Int Int -> Array Int Int</syntaxhighlight>
+
<syntaxhighlight lang="Haskell">convert:: Automaton -> Automaton</syntaxhighlight>
 
<syntaxhighlight lang="Haskell" class="myDark">
 
<syntaxhighlight lang="Haskell" class="myDark">
−
ghci> elems $ quickSort $  listArray (0,5) [8,4,9,6,7,1]
+
ghci>convert ex2
−
[1,4,6,7,8,9]
+
(3, "ab", [(0,'a',1), (0,'b',0), (1,'a',1), (1,'b',2), (2,'a',1), (2,'b',0)], 0, [2],)
 
</syntaxhighlight>
 
</syntaxhighlight>

Latest revision as of 13:03, 10 October 2023

Automatons

Usually, a finite automaton defined as: where Q represents states, next is input alphabet, then transitions (), is starting state and finally there is a set of final states.

In our case, a finite automaton is represented by types: 

type Transition = (Int, Char, Int)
type Automaton = (Int, String, [Transition], Int, [Int])

where:

  • first number N defines number of states - states will be coded by integer numbers in interval ;
  • 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 (q1, a, q2) representing a transition: ;
  • is a number from interval ;
  • finally, there is a list of number representing possible states that are final in defined automaton.

As examples we can use following automatons: 

ex1 :: Automaton 
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, "ab", [(0,'a',1), (0,'a',0), (0,'b',0), (1,'b',2)], 0, [2])

Your task will be to create three functions:

  • First function checks if a given finite automaton is a deterministic finite automaton.
isDeterministic:: Automaton  -> Bool

ghci>isDeterministic ex1
True
ghci>isDeterministic ex2
False
  • 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.
isAccepting:: Automaton -> String -> Bool

ghci>isAccepting ex1 "aab"
True
ghci>isAccepting ex2 "aaa"
False
  • Finally, create a function that takes a non-deterministic automaton and produces it's deterministic equivalent (the output can be very different based on used methodology).
convert:: Automaton -> Automaton

ghci>convert ex2
(3, "ab", [(0,'a',1), (0,'b',0), (1,'a',1), (1,'b',2), (2,'a',1), (2,'b',0)], 0, [2],)
Retrieved from "http://behalek.cs.vsb.cz/wiki/index.php?title=PFP_Homework_1&oldid=3589"