| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
| Can the answer be N if there is no *? | Jurca Razvan | 1559. TruCoders Linguistics | 5 июл 2023 16:43 | 2 |
|
| Can you explain this test? | Mickkie | 1559. TruCoders Linguistics | 5 июл 2023 16:40 | 2 |
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. |
| What about this test? | pperm | 1559. TruCoders Linguistics | 24 янв 2009 07:56 | 6 |
(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? 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 |
| Is concatenation (a0) describe empty set of words?(-) | diver_ru (Fishburg SAAT) | 1559. TruCoders Linguistics | 14 июл 2008 18:48 | 7 |
I think, it describes word a Re diver_ru (Fishburg SAAT) 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 Re: Re Vedernikoff Sergey 23 сен 2007 16:31 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 |
| What answer? :) | pperm | 1559. TruCoders Linguistics | 14 июл 2008 18:28 | 4 |
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 |
| One more test (+) | Sandro (USU) | 1559. TruCoders Linguistics | 30 май 2008 00:02 | 1 |
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. |
| Weak test, or ambiguous task statement(+) | diver_ru (Fishburg SAAT) | 1559. TruCoders Linguistics | 25 сен 2007 23:38 | 5 |
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. Re: diver_ru (Fishburg SAAT) 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 Re: Re: Vedernikoff Sergey 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 Re: Re: Sandro (USU) 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. |
| Tests | Vedernikoff Sergey | 1559. TruCoders Linguistics | 22 сен 2007 18:44 | 1 |
Tests Vedernikoff Sergey 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 |
