31 Mar 2017
Recently 6 teams across Years 7-12 competed in the State round of the OzClo Computational and Linguistics Olympiad. The competitions challenge students to develop their own strategies for solving problems in fascinating real languages. Despite the competition being officially open to Year 9-12 students, two teams from Years 7-8 competed, with distinction. One of our teams, comprising of Brynn Daly, Lily McMahon, Chloe Muir and Kerisha Parkes came second in the State, closely behind the senior team from Baulkham Hills High School. They recently competed in the National Round at the University of Sydney. Congratulations to this team, who have continued their winning ways from their junior days.
Also competing with distinction was the team who placed fourth in the State: Uditha Jith, Isabella Matthews, Cathleen Li and Ellen Zheng.
Do you think you could compete?
Problem 3: Using rules to make strings. In one sense we can think of a sentence as a string or sequence of words. But it's not a random string of course: there are rules. This problem is about a type of rule that builds up (‘generates') strings, but we'll use characters (letters) here instead of words. You start with a string of characters. If your string contains a character that appears on the left side of the arrow in a rule, you can turn that character into whatever is on the right side of the arrow in that rule. You can apply different rules to your string over and over again until no more moves are possible. You're not allowed to twiddle the order of the characters in your string.
Here are the rules: S - AB
A - ab
A - aAb
B - bcd
B - bBc
i. If you start with ‘S', which of these strings is it possible to end up with using these rules? (Put a tick to the right of the possible strings, and a cross to the right of the impossible ones.)
1. abcd
2. abbcd
3. aabbbcd
4. aaabbbcd
5. abbbbcdcc
6. aabbccdcc
7. aabbbbcdc
8. aaabbbbcd
9. aaabbbbcdc
10. aabbbbbcdcc
11. aaabbbbbbcdcc
ii. Here is a string that can not be generated by these rules: bbbbcdccc
Can you add a rule to all the others so that this string can be generated?