a0a* F My WA output N (infinite) I interpret this as (a)concat(0)concat(a*) = {a, aa, aaa, aaaa, ...} This expression describes words of the form xyz, where x comes from the set {a}, y comes from the set {} (i.e. empty set), and z comes from the set {empty_word, a, aa, aaa, ...}. Since y must be an element of an empty set, there is no such word of the form xyz, so the answer is F. (0*|0)a* My AC program output F. But I think than answer N. Other AC program output N Test must be add :) I think, that if there are no '*' symbols, the answer should always be F. Am I right? No, you are not right :) Indeed ? Without '*' what construction can give more 10^100000 words? For example: (a|b)(a|b)....(a|b) gives only 2^2000. How make bigger? Edited by author 24.01.2009 08:00 I think, it describes word a but you have wa... I think that if for "abc" power of set will be (1 * 1 * 1) = 1, for "ab(c|d)" power will be (1 * 1 * 2) = 2, than for (a0) power of set will be 1 * 0 = 0 But why power of the empty set is equal to 0? I think, it is equal to 1... Some hints: 1) power of set (a0) is 0 2) By statement, "it means (if there is '*') <symbol>0|<symbol>1|…|<symbol>n|… (arbitrarily many times) where <symbol>i means <symbol><symbol>…<symbol> (i times) and <symbol>0 means the set consisting of one empty word ", so power of set (0)* is 1, and set (a)* is inifnite Edited by author 23.09.2007 17:00 0 does not mean the set consisting of one empty word, but rather it means an empty set of words. Still, there is a way to obtain a set consisting of one empty word. Edited by author 14.07.2008 18:49 Edited by author 14.07.2008 18:49 a0a* Some test: a0a* F (a0*a)* N 0* F (0*)* N The last one is F, not N. Edited by author 14.07.2008 18:45 I added one more test (thanks to Alexander Kouprin for it). You can see that tests are still weak. If you have some good test send it to timus_support(at)acm.timus.ru. I send two programs, and both got accepted. But for test "(0)**" first program answered "N", second "F". By statement, power of set (0)* is 1, but what is power of set (0)**? 1 or infinity? Edited by author 23.09.2007 20:47 You are wrong. Jury has this test, and all your programs output F on it. F is a correct answer, of course. For any set A, if a power of set A is 1, then power of set A* is infinity. Oh, sorry. This test looks like "(0*)*", and for it both my programs really gives different answers. P.S. hmmm... >>For any set A, if a power of set A is 1, then power of set A* is infinity. But if power of set A=(0)* is 1 (contains one empty word), then power of A* should be infinity, so answer N, isn't it? Or i misunderstand something? Edited by author 25.09.2007 13:32 Empty word + Empty word = Empty word, so we have only one element in (0)* Edited by author 25.09.2007 17:28 Sorry, I was wrong. "For any set A, if a power of set A is 1, then power of set A* is infinity." is correct for A!={empty_word} only. And {empty_word}* = {empty_word}. So (0)* = {empty_word}, and (0)** = {empty_word}, so answer is F. I suggest to everybody post some tests here to test our programs. There are so many WAs... a* => N 0* => F ((a))* => N ((0))* => F 0*|0*|0*|0*|0*|0* => F |
|