/home/scinfo/public_html/index.php:18:string 'ATTENTION: Ce site ne sera plus displonible à partir de Septembre 2017' (length=71)
Deterministic Finate Automata :: Sciences Informatiques (ULg)
Nouveau sujet Répondre Imprimer Syndication RSS 2.0

Deterministic Finate Automata


Assistant
  • Messages : 10
Message édité 5 fois, dernière édition par Emmanouil Psanis, 23 Novembre 2014, 12:00     Lien vers ce message 23 Novembre 2014, 11:55
This thread will list the questions asked by your colleagues.
Feel free to post directly here.
Please consult the forum before asking a question as it may have already been answered.
  1. I get an extremely large error message and most errors come from unitTest.cpp. Is the file corrupted?
If the error message at some point reads:
unitTest.cpp: In function 'int main(int, char**)':
unitTest.cpp:39:85: error: no match for 'operator==' in 'DFA::operator+(DFA&)((* dfa.std::vector<_Tp, _Alloc>::operator[]DFA*,std::allocator<DFA*> >(((i * 3u) + 1u)))) == DFA::operator+(DFA&)((*dfa.std::vector<_Tp, _Alloc>::operator[]<DFA*, std::allocator<DFA*> >(((i *3u) + 1u))))'
unitTest.cpp:39:85: note: candidates are:
DFA.hpp:21:7: note: bool DFA::operator==(DFA&)
DFA.hpp:21:7: note: no known conversion for argument 1 from 'DFA' to 'DFA&'

Then this is because you have defined the operator incorrectly. In my tests, at some point I compare two temporary objects ( A + B == B + A ). This kind of functionality must be supported by your code.

  1. After compiling the tests I got this :

Running 15 tests
----------------
1) Identity test: Is A = A ? Pass
2) Sum test: Is A + B = A + B ? Pass
3) Commutative test: Is A + B = B + A ? Pass
4) Concatenation test: Is A * B = A * B ? Pass
5) Concatenation identity equality test: Is A * A = A * A ? Pass
6) Inequality test: Is A != A ? Pass
7) Inequality test 2: Is A != B and A = B? Pass
8 ) Inequality test 3: Is A != B or A = B? Pass
9) Containment test: Is A <= A ? Pass
10) Union identity equality test: Is A + A = A ? Pass
11) Logic 1: If A <= B and A >= B then A = B? Fail
12) Logic 2: If A != B then A * B != B * A? Pass
13) Associative Law in Union: Is A + (B + C) = (A + B) + C? Pass
FINISHED CPU 0.00 MEM 0 MAXMEM -1 STALE 0

What is the meaning of the last line ?

The last line is the output of a control script. The first word of the last line indicates the exit status:

a) TIMEOUT - time limit is exhausted
b) MEM - memory limit is exhausted
c) HANGUP - hangup detected (see below)
d) SIGNAL - the timeout process was killed by a signal

For completeness, the last two tests are:

14) Associative Law in Concatenation: Is A * (B * C) = (A * B) * C?
15) Distributive Law: Is A * (B + C) = (A * B) + (A * C)?
  1. Why are the two last tests not displayed ?
A combination of FINISHED status without all the tests being displayed signifies a core dumped.

Assistant
  • Messages : 10
Message édité 4 fois, dernière édition par Emmanouil Psanis, 29 Novembre 2014, 13:02     Lien vers ce message 29 Novembre 2014, 2:43
Dear all,

Here is some help on DFA concatenation. When we merge two DFA nodes it practically means the we might be in any of the states. This applies both on union and concatenation. If for example we have:
DFA_1
-----
A
0 --> A
1 --> B (final)
2 --> A

B (final)
0 --> A
1 --> A
2 --> A

DFA_2
-----
C
0 --> D
1 --> C
2 --> E (final)

D
0 --> D
1 --> C
2 --> D

E (final)
0 --> D
1 --> D
2 --> D

Then for the concatenation DFA we have:
Node A
0 --> A
1 --> B_C //We are in DFA_1 state B and DFA_2 state C concurrently. Since state C does not accept, B_C is not final
2 --> A

Node B_C
0 --> A_D //If we were still in DFA_1 we would be in node A, but if we passed to DFA_2 we will be in D. We are concurrently in both states
1 --> A_C //Similar as above
2 --> A_E (final) //We are concurrently in DFA_1-Node A and DFA_2-Node E and since E is final, we accept

Node A_D:
0 --> A_D //Because delta(A_D,0) = delta(A,0)_delta(D,0) = A_D
1 --> B_C //Similarly
2 --> A_D

Node A_C:
0 --> A_D //delta(A_C,1) = delta(A,1)_delta(C,1) = B_C_C because now that we merged B with C we are in both states with an epsilon transition (concurrently)
1 --> B_C // but B_C_C means that we are concurently in states B, C and C ==> in states B and C, thus delta(A_C,1) = B_C, see below
2 --> A_E (final)

Node A_E (final)
0 --> A_D
1 --> B_C_D //This is the key! One might expect the target node to be delta(A_E,1) = delta(A,1)_delta(E,1) = B_D but remember that now node B is
2 --> A_D //replaced by node B_C stating that we are concurrently in B and C. So delta(A,1) = B_C now that we are in the new path, thus
//delta(A_E,1) = delta(A,1)_delta(E,1) = B_C_D. Also, in node A_C above, delta(A_C,1) = delta(A,1)_delta(C,1) = B_C_C but we have a repetition of C, so we merge into node B_C!

Node B_C_D:
0 --> A_D //delta(B_C_D,0) = delta(B,0)_delta(C,0)_delta(D,0) = A_D_D ==> A_D
1 --> A_C
2 --> A_E_D (final) //because E is an accepting state of the rhs DFA

Node A_E_D (final)
0 --> A_D
1 --> B_C_D
2 --> A_D

As you may see, B never appears by itself on the concatenation DFA! In summary, when we need the name/ transitions of the final state under examination of the lhs DFA we use the replacement name / transitions, instead (here instead of node B we use node B_C)

3ème Bac.
  • Age : 24 ans
  • Messages : 2
  Lien vers ce message 29 Novembre 2014, 17:38
Dear Mr Psanis,
Could you please confirm the submission date of this project, because in the assignment you say : "Projects must be submitted before Monday November 30, 11:59pm."
And on the platform it is written : 01/12/2014 00:00
Besides, Monday is December 1, so should we submit before Sunday at midnight, or do we have until Monday at midnight to do so?

Regards

Assistant
  • Messages : 10
  Lien vers ce message 30 Novembre 2014, 14:11
Deadline: Sunday November 30, 11:59
The platform closes 1 minute after the deadline.
Répondre


.