| ENG RUS | Timus Online Judge |
Обсуждение задачи 1559. TruCoders LinguisticsJurca Razvan Can the answer be N if there is no *? [1] // Задача 1559. TruCoders Linguistics 13 май 2009 18:01 Markadiusz Re: Can the answer be N if there is no *? // Задача 1559. TruCoders Linguistics 5 июл 2023 16:43 No. Mickkie Can you explain this test? [1] // Задача 1559. TruCoders Linguistics 12 ноя 2020 21:37 a0a* F My WA output N (infinite) I interpret this as (a)concat(0)concat(a*) = {a, aa, aaa, aaaa, ...} Markadiusz Re: Can you explain this test? // Задача 1559. TruCoders Linguistics 5 июл 2023 16:40 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. pperm What about this test? [5] // Задача 1559. TruCoders Linguistics 5 окт 2007 12:40 (0*|0)a* My AC program output F. But I think than answer N. pperm Re: What about this test? [4] // Задача 1559. TruCoders Linguistics 5 окт 2007 12:53 Other AC program output N Test must be add :) SPIRiT Re: What about this test? [3] // Задача 1559. TruCoders Linguistics 6 ноя 2007 18:04 I think, that if there are no '*' symbols, the answer should always be F. Am I right? Sandro (USU) Added (-) // Задача 1559. TruCoders Linguistics 7 ноя 2007 00:23 Denis Koshman Re: What about this test? [1] // Задача 1559. TruCoders Linguistics 14 июл 2008 18:29 No, you are not right :) svr Re: What about this test? // Задача 1559. TruCoders Linguistics 24 янв 2009 07:56 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 diver_ru (Fishburg SAAT) Is concatenation (a0) describe empty set of words?(-) [6] // Задача 1559. TruCoders Linguistics 23 сен 2007 15:09 Vedernikoff Sergey Re: Is concatenation (a0) describe empty set of words?(-) [5] // Задача 1559. TruCoders Linguistics 23 сен 2007 15:28 I think, it describes word a diver_ru (Fishburg SAAT) Re [4] // Задача 1559. TruCoders Linguistics 23 сен 2007 15:37 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 Vedernikoff Sergey Re: Re [3] // Задача 1559. TruCoders Linguistics 23 сен 2007 16:31 But why power of the empty set is equal to 0? I think, it is equal to 1... diver_ru (Fishburg SAAT) AC at last(+) [2] // Задача 1559. TruCoders Linguistics 23 сен 2007 16:58 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 Vedernikoff Sergey Re: AC at last(+) // Задача 1559. TruCoders Linguistics 23 сен 2007 17:41 Thanks Denis Koshman Re: AC at last(+) // Задача 1559. TruCoders Linguistics 14 июл 2008 18:48 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 pperm What answer? :) [3] // Задача 1559. TruCoders Linguistics 3 окт 2007 18:45 a0a* pperm AC now :) [2] // Задача 1559. TruCoders Linguistics 3 окт 2007 19:16 Some test: a0a* F (a0*a)* N 0* F (0*)* N Гладких Максим Re: AC now :) // Задача 1559. TruCoders Linguistics 22 июн 2008 21:18 The last one is F, not N. Denis Koshman Re: AC now :) // Задача 1559. TruCoders Linguistics 14 июл 2008 18:28 Edited by author 14.07.2008 18:45 Sandro (USU) One more test (+) // Задача 1559. TruCoders Linguistics 30 май 2008 00:02 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. diver_ru (Fishburg SAAT) Weak test, or ambiguous task statement(+) [4] // Задача 1559. TruCoders Linguistics 23 сен 2007 17:34 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 Sandro (USU) Re: Weak test, or ambiguous task statement(+) [3] // Задача 1559. TruCoders Linguistics 25 сен 2007 11:24 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. diver_ru (Fishburg SAAT) Re: [2] // Задача 1559. TruCoders Linguistics 25 сен 2007 13:13 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 Vedernikoff Sergey Re: Re: [1] // Задача 1559. TruCoders Linguistics 25 сен 2007 17:28 Empty word + Empty word = Empty word, so we have only one element in (0)* Edited by author 25.09.2007 17:28 Sandro (USU) Re: Re: // Задача 1559. TruCoders Linguistics 25 сен 2007 23:38 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. Vedernikoff Sergey Tests // Задача 1559. TruCoders Linguistics 22 сен 2007 18:44 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
|