PFP Homework 2 - Revision history

Beh01: /* Automatons II */

2023-10-10T17:54:16Z

Automatons II

Beh01: /* Automatons II */

2023-10-10T17:27:39Z

Automatons II

Beh01: Created page with "= Automatons II = Usually, a finite automaton defined as: $(Q, \Sigma, \delta, q_0, F)$ where Q represents states, next is input alphabet, then transitions ( $..."$

2023-10-10T13:32:20Z

Created page with "= Automatons II = 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>..."

New page

= Automatons II =
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">
type Transition = (Int, Char, Int)
type Automaton = (Int, String, [Transition], Int, [Int])
</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.

As examples we can use following automatons:
<syntaxhighlight lang="Haskell">
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])
</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>

@@ Line 23: / Line 23: @@
 </syntaxhighlight>
 <syntaxhighlight lang="Haskell">
@@ Line 32: / Line 37: @@
 </syntaxhighlight>
-Your task will be to create three functions:
+As an example we can use following regular expression:
 <syntaxhighlight lang="Haskell" class="myDark">
-ghci>isDeterministic ex1
+ghci>convert reg1
-True
+(3, "ab", [(0,'a',1), (0,'a',0), (0,'b',0), (1,'b',2)], 0, [2])
 </syntaxhighlight>

@@ Line 21: / Line 21: @@
 ex2 :: Automaton
 ex2 = (3, "ab", [(0,'a',1), (0,'a',0), (0,'b',0), (1,'b',2)], 0, [2])
 </syntaxhighlight>

PFP Homework 2 - Revision history

Beh01: /* Automatons II */

Beh01: /* Automatons II */

Beh01: Created page with "= Automatons II = Usually, a finite automaton defined as: (Q, \Sigma, \delta, q_0, F) where Q represents states, next is input alphabet, then transitions (..."

Beh01: Created page with "= Automatons II = Usually, a finite automaton defined as: $(Q, \Sigma, \delta, q_0, F)$ where Q represents states, next is input alphabet, then transitions ( $..."$