Problem
We will play a game called TKO. We start with n players with names {1, ..., n}. In each round of the game, all surviving players participate, and exactly one of them wins the round. After every round, players who are "too far behind" drop out; the rule for "too far behind" is as follows: players who have won ten fewer games than some other player drop out.
Players who drop out do not survive the round. The game can end in any round after a round is played in which there is only one surviving player.
We record the game play as a string in {1,...,n}*, where the ith character in the string is the winner of round i.
Then the language of TKO games is the set of all strings that can be the game play for TKO.
• Is the language of TKO games with two players regular? Prove by pumping lemma.
Suppose we changed the requirement of dropping out to be: no player drops out in the first 10 rounds. After that, players who have won fewer than half the number of rounds won by some other player drop out.
a) Is this modified TKO with two players regular? Prove by pumping lemma.
b) Show that modified TKO is context-free by creating a visual pushdown automata.