Search code examples
dfadecidable

Show that the language is decidable

How do I show this language

{<C,A,B> | C,A,B are DFAs, L(C) contains the shuffle of L(A) and L(B)}

is decidable ?

I believe if I can construct automatas for A and B, then I can get an automata that contains the shuffle of them.

I am also thinking about using emptiness testing but I have not made any progress yet.

Solution

    1. Given DFAs A and B, construct a DFA D such that L(D) is equal to the shuffle of L(A) and L(B).

    2. Then, construct two DFAs using the Cartesian Product Machine construction for the languages L(M1) = L(C) \ L(D) and L(M2) = L(D) \ L(C).

    3. Determine which, if either of L(M1) and/or L(M2) is empty.

      • if L(M1) is empty and L(M2) is empty, L(C) is the shuffle of L(A) and L(B)
      • if L(M1) is empty, L(C) is a subset of the shuffle of L(A) and L(B)
      • if L(M2) is empty, L(C) is a superset of the shuffle of L(A) and L(B)

    To do #1: create a new DFA whose states are triples (x, y, z) where:

    1. x is a state from A
    2. y is a state from B
    3. z is either 1 or 2

    The initial state of the DFA will be (qi_A, qi_B, 1). The input alphabet will be the union of the input alphabets of A and B. The transitions will be such that:

    • f((x,y,1), a) = (x',y,2) where f(x,a) = x' in machine A
    • f((x,y,2), b) = (x,y',1) where f(y,b) = y' in machine B

    The accepting states shall be the states with are accepting in either A or B (or just B if you prefer).

    To do #2: create a new DFA whose states are pairs (x, y) where:

    1. x is a state from D
    2. y is a state from C

    The initial state of he DFA will be (qi_D, qi_C). The input alphabet will be the union of input alphabets of A and C. The transitions will be such that:

    • f((x,y),c) = (x',y') where f(x,c) = x' in D and f(y,c) = y' in C.

    The accepting states will be:

    • states that are accepting in D but not C, for L(D) \ L(C)
    • states that are accepting in C but not D, for L(C) \ L(D)

    To do #3:

    1. You can minimize the DFAs using the well-known DFA minimization algorithm. Iff you end up with a DFA that has a single non-accepting state, the language is empty.

    2. You can try all input strings up to the pumping length for the resulting DFA (strings that don't cause the DFA to enter any state more than once). If none of these are accepted by the DFA, then the DFA accepts no strings and the language is empty.