DFA in SQL Modellieren

[Kirby.exe]

Alsoo wir sollen folgenden DFA modellieren:



Dieser soll überprüfen ob eine Binärzahl durch 3 teilbar ist Ich habe bis jetzt schon recht viel, aber ich verstehe die Fehlermeldung nicht ganz

Das ist die Fehlermeldung:

Fehler in der SQL-Abfrage (7): ERROR: recursive query "dfa" column 2 has type text in non-recursive term but type character varying overall
LINE 3: inputs.str, 'S0', inputs.str
HINT: Cast the output of the non-recursive term to the correct type.

Das ist mein bisheriger Code:

CREATE TABLE rules (current_state VARCHAR(2), chr VARCHAR(2), next_state VARCHAR(2));
INSERT INTO rules VALUES
  ('S0', '0', 'S0'), ('S0', '1', 'S1'),
  ('S1', '0', 'S2'), ('S1', '1', 'S0'),
  ('S2', '0', 'S1'), ('S2', '1', 'S2');

CREATE TABLE accept_states (current_state VARCHAR(2), accepted BOOLEAN);
INSERT INTO accept_states VALUES ('S0', true), ('S1', false), ('S2', false);

CREATE TABLE inputs (str TEXT);
INSERT INTO inputs VALUES ('10010'), ('010010010'), ('011');

WITH RECURSIVE dfa(source, current_state, work) AS (
  SELECT
    inputs.str, 'S0', inputs.str
  FROM
    inputs
  UNION ALL
  SELECT
    source,
    next_rules.next_state,
    SUBSTR(dfa.work, 2, 10)
  FROM
    dfa JOIN (SELECT * FROM rules) AS next_rules ON dfa.current_state = next_rules.current_state
  WHERE
    chr = SUBSTR(dfa.work, 1, 1)
)
SELECT
  source,
  accepted
FROM
  dfa JOIN accept_states ON dfa.current_state = accept_states.current_state
WHERE
  work = '';

DROP TABLE rules;
DROP TABLE accept_states;
DROP TABLE inputs;

 

[mrBrown]

Deine recursive Query dfa hat in Spalte 2 (= current_state) den Type Text im nicht rekursiven Term (konkret den Wert 'S0'), benötigt wird aber VARCHAR(2).

Lösen kannst du das mit einem Cast von 'S0' zu Varchar(2)

 

[Kirby.exe]

Jetzt funktioniert es danke

 

[Barista]

Ich wusste nicht, dass dies funktioniert und habe es mal mit Java ausprobiert.

Zu meinem Erstaunen klappt es:
[CODE lang="java" title="DfaMultipleOf3"]import java.util.Arrays;

/**
* https://www.java-forum.org/thema/dfa-in-sql-modellieren.192126/
*/
public class DfaMultipleOf3
{
/**
* State of DFA
*/
static class State
{
final String name;

/**
* is accepting state.
*/
final boolean isAcceptingState;

/**
* successor state for value 0.
*
* Not final because there is a circular reference.
*/
State _0;

/**
* successor state for value 1.
*
* Not final because there is a circular reference.
*/
State _1;

/**
* Constructor.
*
* @param name
* @param isAcceptingState
*/
State(
final String name ,
final boolean isAcceptingState )
{
this.name = name;
this.isAcceptingState = isAcceptingState;
}

@Override
public String toString()
{
return this.name;
}
}

static final State dfa =
createDfa();

private static State createDfa()
{
// start state
final State s0 =
new State(
//name
"S0" ,
//isAcceptingState
true );

final State s1 =
new State(
//name
"S1" ,
//isAcceptingState
false );

final State s2 =
new State(
//name
"S2" ,
//isAcceptingState
false );

s0._0 = s0;
s0._1 = s1;

s1._0 = s2;
s1._1 = s0;

s2._0 = s1;
s2._1 = s2;

return s0;
}

/**
* Returns is the given number a multiple of 3.
*
* @param numberToCheck
* @return is the given number a multiple of 3
*/
public static boolean isMultipleOf3(
int numberToCheck )
{
if ( numberToCheck < 0 )
{
throw new IllegalArgumentException( String.valueOf( numberToCheck ) );
}

boolean[] digits = new boolean[ 0 ];

while ( numberToCheck > 0 )
{
final boolean[] tmpDigits = new boolean[ digits.length + 1 ];

tmpDigits[ 0 ] = numberToCheck % 2 == 1;

System.arraycopy(
//src
digits ,
//srcPos
0 ,
//dest
tmpDigits ,
//destPos
1 ,
//length
digits.length );


digits = tmpDigits;

numberToCheck /= 2;
}

return isMultipleOf3( digits );
}

private static boolean isMultipleOf3(
final boolean[] digitsToCheck )
{
System.out.println( Arrays.toString( digitsToCheck ) );
State currentState = dfa;

for ( int i = 0 ; i < digitsToCheck.length ; i++ )
{
final boolean digit = digitsToCheck[ i ];
System.out.print( ( digit ? "1" : "0" ) + ": " + currentState + " => " );

if ( ! digit )
{
currentState = currentState._0;
}
else
{
currentState = currentState._1;
}

System.out.println( currentState );
}

return currentState.isAcceptingState;
}

}
[/CODE]

Hier noch der JUnit4 Test:

[CODE lang="java" title="DfaMultipleOf3Test"]import org.junit.Assert;
import org.junit.Test;

public class DfaMultipleOf3Test
{

@Test
public void testIsMultipleOf3()
{
final int MAX = 100;

for ( int i = 0 ; i <= MAX ; i++ )
{
System.out.println( i + " " + Integer.toBinaryString( i ) );

final boolean isMultipleOf3 =
DfaMultipleOf3.isMultipleOf3(
//numberToCheck
i );

System.out.println( isMultipleOf3 );

if ( i % 3 == 0 )
{
Assert.assertTrue( isMultipleOf3 );
}
else
{
Assert.assertFalse( isMultipleOf3 );
}

System.out.println( "=======================" );
}
}

}
[/CODE]