A***e
发帖数: 130 | 1 yes, non-deterministic
roughly to say,
use separate path, each compare the i-th symbol in A and B, where i=1, ... |A|
if any pair is different, output "yes".
Because i is finite, the above automata (actually a PDA) works. | c*****t
发帖数: 1879 | 2 A bit strange how your i is defined. What did you mean by finite?
I remembered that I posted a solution in this board for L != ww by giving a
formula. Couldn't find it anymore :(
It was something like:
L = AB | BA | A | B
A = aAa | aAb | bAa | bAb | a
B = aBb | aBb | bBa | bBb | b
The trick was that A and B had different centers.
I guess that for this problem, should be nearly the same.
Or, one could argue that given L != ww is in CFG, one could always
build a stack machi
【在 A***e 的大作中提到】
: yes, non-deterministic
: roughly to say,
: use separate path, each compare the i-th symbol in A and B, where i=1, ... |A|
: if any pair is different, output "yes".
: Because i is finite, the above automata (actually a PDA) works.
| A***e
发帖数: 130 | 3 The main point is the non-deterministic: we can construct
the following PDA:
for each input symbol, depending on what it is and what's the current state
of the PDA, we can do the following actions (with the help of two flags:
A: having passed symbol c or not, and B: having passed the particular symbol for
comparison or not):
1) if it's not c, and the current state has neither flag A nor B set then:
(a) push it onto the stack
-or-
(b) store the symbol into the current state a
【在 c*****t 的大作中提到】
: A bit strange how your i is defined. What did you mean by finite?
: I remembered that I posted a solution in this board for L != ww by giving a
: formula. Couldn't find it anymore :(
: It was something like:
: L = AB | BA | A | B
: A = aAa | aAb | bAa | bAb | a
: B = aBb | aBb | bBa | bBb | b
: The trick was that A and B had different centers.
: I guess that for this problem, should be nearly the same.
: Or, one could argue that given L != ww is in CFG, one could always
| A***e
发帖数: 130 | 4
hmm, by the meaning of "non-deterministic", each sequence of
choices of a/b in case1 (i.e., one path) will only compare *one* symbol in A
and B., and there are multiple paths. In the example you gave, 1100c1100,
there are 4 paths, 1xxxc1, #1xxc#1, ##0xc##0, and ###0c###0, all of them
do not accept. 'x' means taking no action at all, # means that the symbol
will be pushed onto the stack but what it actually is does not matter, only
the it's count matters.
So, there is no need to reverse, and act
【在 c*****t 的大作中提到】
: A bit strange how your i is defined. What did you mean by finite?
: I remembered that I posted a solution in this board for L != ww by giving a
: formula. Couldn't find it anymore :(
: It was something like:
: L = AB | BA | A | B
: A = aAa | aAb | bAa | bAb | a
: B = aBb | aBb | bBa | bBb | b
: The trick was that A and B had different centers.
: I guess that for this problem, should be nearly the same.
: Or, one could argue that given L != ww is in CFG, one could always
| c*****t
发帖数: 1879 | 5 I think that I got what you were saying and it was indeed correct.
Apparently, I didn't notice that you pop all the symbols until the
very last token (there are some technicality there, but definitely
doable) then do the comparison. Basically one comparison for each
non-deterministic path.
I think that it will be very difficult if not impossible to come up
with a CFG for this grammar.
【在 A***e 的大作中提到】
:
: hmm, by the meaning of "non-deterministic", each sequence of
: choices of a/b in case1 (i.e., one path) will only compare *one* symbol in A
: and B., and there are multiple paths. In the example you gave, 1100c1100,
: there are 4 paths, 1xxxc1, #1xxc#1, ##0xc##0, and ###0c###0, all of them
: do not accept. 'x' means taking no action at all, # means that the symbol
: will be pushed onto the stack but what it actually is does not matter, only
: the it's count matters.
: So, there is no need to reverse, and act
| b***e
发帖数: 1419 | 6
A -> 0 | 1 -- alphabet
B -> c | ABA -- balanced string
U -> B(A+) | (A+)B -- unbalanced string
X -> 0 | AXA
X1 -> Xc | A(X1)A
X2 -> cX | A(X2)A
Y -> 1 | AYA
Y1 -> Yc | A(Y1)A
Y2 -> cY | A(Y2)A
S -> U | X(Y2) | (Y1)X | (X1)Y | Y(X2)
【在 c*****t 的大作中提到】
: I think that I got what you were saying and it was indeed correct.
: Apparently, I didn't notice that you pop all the symbols until the
: very last token (there are some technicality there, but definitely
: doable) then do the comparison. Basically one comparison for each
: non-deterministic path.
: I think that it will be very difficult if not impossible to come up
: with a CFG for this grammar.
|
|
