wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> DFA Design: LR and RL Products
        
(Message started by: william wu on Jan 29^th, 2003, 4:39pm)

Title: DFA Design: LR and RL Products
Post by william wu on Jan 29^th, 2003, 4:39pm

Imagine a world where multiplication over the symbols a, b, and c is defined as follows:

Code:

a b c
------------------------------
a | a a c
b | c a b
c | b c a

(interpret this table as saying a*a = a, b*c = b, and so on)

Given a string S = "s₁s₂ ... s_n" composed of symbols a, b, and c, define the LR-Product of S as follows:

LR-Product(S) = ( ... (((s₁ * s₂) * s₃) * s₄) ... )

This essentially says multiply the first two digits, then take that product and multiply it by the third digit, then take that product and multiply it by the fourth digit, and so on, processing the string in this fashion from left to right. Similarly, define the RL-Product of S as follows

RL-Product(S) = ( ... (((s_n-1 * s_n) * s_n-2) * s_n-3) ... )

This does the same thing, but moving from right to left.

Problem: Design a deterministic finite automaton ( a finite state machine) that accepts all strings over the alphabet {a,b,c} whose LR-Product and RL-Product are identical.

Note 1: From Ranjit Jhala, UCB CS172 Discussion 1/29/2003
Note 2: Note that the desired language is not quite a language of palindromes. There is no DFA which can accept palindromes.
Note 3: If you are unfamiliar with the terminology, feel free to ask. Or you can google search for lecture notes.

Title: Re: DFA Design I
Post by James Fingas on Jan 30^th, 2003, 11:56am

It seems to me that the key could be to perform the RL product backwards (starting with the last multiplication first), always maintaining the current LR and RL products. When you get to the end of the string, the products should be the same.

I just can't figure out a way to reverse that particular transformation...it's just so non-linear. And that means that the multiplication isn't commutative. Do we really have to contend with a*b=a? Bleah!

At each step, you would have to decide what the RL product would have to be for other (unknown) part of the input sequence.

RL_i-1 * s_i = RL_i

We are given RL_i and s_i, and we have to figure out RL_i-1. this table gives the various values for RL_i-1 for given values of RL_i and s_i

s_i
a b c
R a a a,b c
L b c - b
i c b c a

The only problem occurs when we have RL_i = a and s_i = b. In this case, we would obviously need to maintain two branches to take care of the two possibilities. However, the next step won't erase one of these branches. For instance, s_i+1 = a allows both branches to live, and s_i+2 = b then gives three branches. I suppose the most you could ever get to would be three branches though. Maybe this is possible...

Title: Re: DFA Design I
Post by towr on Jan 31^st, 2003, 2:21am

If the first row was a b c, instead of a a c, it would be a lot easier, I think..

Title: Re: DFA Design I
Post by william wu on Jan 31^st, 2003, 4:05am

Yea I see what you're saying. I'm stuck on this problem too, and I e-mailed the source to make sure the multiplication table is right. I'll let you guys know what he says.

Title: Re: DFA Design I
Post by James Fingas on Jan 31^st, 2003, 10:56am

Okay, I've been thinking some more about this:

We'll have four finite state machines working at once to solve this problem (one to compute the LR product, and three to figure out what the RL product would be, when reading the sequence in forwards). The machines will start out initialized to a, b, and c, corresponding to the three RL products that we could end up with.

The three RL machines will remember this RL product throughout the whole operation. It will a single input--the value of s_i. It will also have a register which stores what the RL-product of the remaining terms must be to produce the given final RL product.

Code:

ordinal S = {a,b,c};

class RL_state_machine {
S end_RL_product;
S remaining_RL_product;
method compute_next_product( S s_i );
}

class LR_state_machine {
S current_LR_product;
method compute_next_product( S s_i );
}

boolean accepted(RL_machineA, RL_machineB, RL_machineC, LR_machine, s_i);

The LRmachine is easy to implement. All you do is compute the next value for the LR product given the current LR product and the following table (this is the transition table William gave):

L s_i
R a b c
i a a a c
- b c a b
1 c b c a

To initialize the LR_state_machine, you set the current LR product to the first s_i. When you get to the last input, you use it to compute the final LR product. That's all!

The RL_state_machine is a little more difficult. You initialize the three machines to have end_RL_products equal to "a", "b", and "c" respectively. You also initialize the remaining_RL_product to "a", "b", and "c" respectively. With each s_i you read in (including the first), you backtrack one step, figuring out what the previous remaining_RL_product must have been. You use the following transition table:

s_i
a b c
R a a b c
L b c a* b
i c b c a

However, you will notice this is different from the table I have last time. I have split it up so that only one possibility gets assigned to each machine. The catch here is that if the current remaining_RL_product is "b" and s_i is also "b", then not only do you set remaining_RL_product to "a", but you also change the end_RL_product. You have to change it to be the same as the end_RL_product of the machine that had the remaining_RL_product of "a" during that step.

When you get to the final s_i, you don't compute the next remaining_RL_product with it, but instead you just use it in the string acceptance check.

Now all I have to do is address the string acceptance check. First, you compute which RL_machines are possible candidates, by seeing which machines have an end_RL_product matching the current_LR_product in your LR machine. Then, you check if any of those candidate RL machines (it could be all three of them!) have remaining_RL_products equal to the last s_i. If one does (there can only be one) then the string is acceptable. QED!

Now I will try and illustrate with an example. I'm hoping this will lend support to my solution instead of showing that it doesn't work ;)

Consider the string a b c b c. The RL and LR products are the same for this one. I will try to show the steps here:

1) You read in "a", and initialize your LR machine to "a". Your three RL machines will be initialized to a, b, and c respectively. With this first s_i, they will take on the values a, b, and c respectively.
LR machine: current_LR_product = a
RL machineA: end_RL_product = a, remaining_RL_product = a
RL machineB: end_RL_product = b, remaining_RL_product = b
RL machineC: end_RL_product = c, remaining_RL_product = c

2) You read in "b".
LR machine: current_LR_product = a
RL machineA: end_RL_product = a, remaining_RL_product = b
RL machineB: end_RL_product = a, remaining_RL_product = a
RL machineC: end_RL_product = c, remaining_RL_product = c

3) You read in "c".
LR machine: current_LR_product = c
RL machineA: end_RL_product = a, remaining_RL_product = b
RL machineB: end_RL_product = a, remaining_RL_product = c
RL machineC: end_RL_product = c, remaining_RL_product = a

4) You read in "b".
LR machine: current_LR_product = c
RL machineA: end_RL_product = c, remaining_RL_product = a
RL machineB: end_RL_product = a, remaining_RL_product = c
RL machineC: end_RL_product = c, remaining_RL_product = b

5) You read in "c".
LR machine: current_LR_product = a
Don't compute the RL products, just check to see whether or not our acceptance criteria have passed. The only candidate machine is RL machineB, because it has an end_RL_product of "a", which matches our final LR product. Furthermore, you can see that the remaining_RL_product is "c", which matches the input. Therefore, the string is accepted!
RL machineB: end_RL_product = a, remaining_RL_product = c

Woohoo! Of course, the four finite state machines can be combined into one large finite state machine, and with a little thought to the timing of things, I think it's implementable.

Title: Re: DFA Design: LR and RL Products
Post by william wu on Mar 9^th, 2003, 8:05pm

Turns out that it doesn't matter what the contents of the multiplication table are ... it's completely arbitrary.

Here is a high-level description of a solution, which only came to me after learning some very cool closure properties about regular languages. (Regular language = a set of strings that can be accepted by a deterministic finite automaton, or equivalently by a Regular Expression, or equivalently by a nondeterministic finite automaton.) Here goes; sorry it's a bit verbose:

[hide]
Overview of approach: Break this up into 6 subproblems:

machine M1: strings that evaluate to a when read left to right
machine M2: strings that evaluate to a when read right to left
machine M3: strings that evaluate to b when read left to right
machine M4: strings that evaluate to b when read right to left
machine M5: strings that evaluate to c when read left to right
machine M6: strings that evaluate to c when read right to left

I will use and briefly prove the following closure properties,

1. Regular languages are closed under reversal.
2. Regular languages are closed under intersection.
3. Regular languages are closed under disjunction.

If we can make M1, we will also be able to make M3 and M5, since they are structurally identical, only differing in which state is marked as accepting.

Since regular languages are closed under reversal, we can also make machines M2, M4, and M6.

Since regular languages are closed under intersection, we can intersect M1 and M2 to make a machine Ma that accepts all strings that evaluate to a when read either left to right or right to left. Likewise we can make Mb, which accepts all strings that evaluate to b when read in either direction, and Mc, which accepts all strings that evaluate to c when read in either direction.

Since regular languages are closed under disjunction, the final machine is M = Ma | Mb | Mc.

First construct state machine M1, which accepts all strings which evaluate to "a" when read left to right. This should be a very straightforward task which just comes down to implementing the multiplication table as a state machine, and marking the state that means "evaluate to a" as accepting. Using my 1337 xfig skills I drew the following machine, which I don't bother hiding:

http://www.ocf.berkeley.edu/~wwu/images/riddles/DFA_LRproduct_a.jpg

(Invoking reversal closure) Now we want a machine M2 that accepts strings which evaluate to a when read right to left. This is accomplished by reversing the directions of all arrows, changing the accepting state to an initial state, and changing the initial state to an accepting state. You can think about why this is true ... I also found it a bit troubling at first, but after a while I guess it's obvious. You're just traversing the same paths that M1 would have, but in reverse.

(Invoking intersection closure) We want to intersect the languages accepted by M1 and M2, to get a new machine Ma. This can be done with a cross product construction. The states of Ma will correspond to cross product pairs (x,y) of the states in M1 and M2. Then the accepting states in Ma are those where x was an accepting state in M1, and y was an accepting state in M2. Intuitively you can think of this cross product machine as running two submachines in parallel. The super machine only accepts iff BOTH of the submachines are in accepting states.

Making machines Mb and Mc follows trivially from the above arguments.

(Invoking closure under disjunction): To make M = Ma | Mb | Mc and complete the problem, we do the same cross product construction to run all three machines in parallel, such that every state is denoted by an (x,y,z) pair, where x was a state in Ma, y was a state in Mb, and z was a state in Mc. Then the super machine accepts iff -- surprise surprise -- AT LEAST ONE of the submachines is in an accepting state. The End.

Additional note about closure under disjunction: if you believe that nondeterministic finite automata <--> determinisitc finite automata, then the disjunction proof is very easy. Just make a new initial state with empty string transitions to Ma, Mb, and Mc. Then the supermachine nondeterministically chooses which of the three machines to use. By definition, a nondeterministic machine accepts if there exists at least ONE accepting branch of computation among the many possible branches it could take.
[/hide]

If anyone is really interested in this stuff, you can think about how to prove some other closure properties of regular languages. Your proofs should be sweet and very short:

1. kleene star: if L is regular, then L* is regular
2. complementation: if L is regular, then NOT(L) is regular
3. difference: if L1 and L2 are regular, then L1 - L2 is regular
4. concatenation: if L1 and L2 are regular, then L1L2 is regular

(proofs for the following are less short than the others, but still short)
5. homomorphism: if L is regular on the alphabet Sigma, then its homomorphic image h(L) is regular the alphabet Gamma.
6. right quotient: if L1 and L2 are regular, then the right quotient of L1 with L2, denoted by L1/L2, is also regular. definition of right quotient:

L1 / L2 = { w : (wx is in L1) AND (x is in L2) }