MadeEasy Test Series: Theory Of Computation - Finite Automata

Question

Consider a Game played be between two players (Player-1, Player-2) repeatedly flip a coin.
On output as a head, Player-1 get a point
On output as a tail, Player-2 get a point
A player wins if his score reaches 2 points before the other player by reaching final state. Which of the following depicts NFA for above problem? 

Can anyone explain how this diagram is working between two players,,,,please?????

Answer 1

The game would finish as soon as we get two consecutive heads or tails/

If after getting a head we get a tail, we are one step away from finishing the game. So we move to that state, in the downward direction.

We can extend this logic to the time when we get one tail and after that, we get a head.

Comments

I understand what you say. But still am having some problems. Here are some of my doubts :-

1.How is the game going on? Are the players playing alternatively?

If yes then, starting with player 1, if HTH comes then player 1 gets 2 points and the game ends.

[HTH means player1 flips head, player2- tail and again player1 head]

Similarly if player2 starts playing then, THT means player2 wins.

But here in the DFA, we don't reach to any final state on such sequences.

2. If they are playing simultaneously with different coins then, on which basis are we creating the sequences? I mean if they both get H on 1st toss how will we represent it? HH looks like player2 tossed after player1.

3. In the solution, H(TH)*H seems like a player starting with H must also end with H (that player is the player1). But what does (TH)* indicate? The T may indicate the 2nd player's toss then H must indicate the 1st player right? The HTH should take us to final state as player1 has already tossed 2 heads.

If (TH)* indicates tosses of the same player who keeps on attempting until 2 heads then also HTH should take to the final state.

Please clear me the whole scenario. Thanks in advance

---

Sir...my question is are both players playing on same dfa and also alternatively?????

Suppose the states are marked as q0 is starting state,,, the states beside q0 ...horizontally are marked as q1 and q2(final state) .....vertically are marked as q3 and q4( final state)

Suppose player1 starts the game....and they are playing alternatively...

Lets take the sequence HTH....player1 at q0 on H moves to q1....then player2 at q1 on T moves to q3....then player1 at q3 on H moves to q1.....so player1 gets 2 point and win but he is in the state q1....which is not the final state......so am I explaining correctly...or else the game is played in different way....plz explain....????

Thanks in advance....

---

You are right - I think the question is ill formed. Modeling this game using a DFA without properly stating all the assumptions would lead to confusion. I tried my best to interpret it, but now I realise this isn't exactly correct either.

---

@Arjun Sir....can u please explain how this game is represented using this dfa