0

Accepted strings would be {"", 11, 100, 1010, 1111} And it would reject everything that is not even length or it ends with a 0.

I constructed two dfa, one that accepts all possible even combinations, and one that ends with a 0, but I can't combine them.

After a bit of thinking, I kinda believe that three states must be enough, but still can't make it work.

Any help is greatly appreciated. enter image description here

Sachihiro
  • 119

1 Answers1

0

I originally misread the question, this should be the corrected answer:

State 1 is initial, states 1 and 2 are terminal (i.e. accepting).

enter image description here

There are three relevantly distinct possibilites at each step:

  1. The current number of characters is even; accepting.
  2. The current number of characters is odd, but the last character was zero; accepting.
  3. The current number of characters is odd and the last character was a one; rejecting.
Jan Matula
  • 316
  • You are right, I misread. I just corrected the answer. – Jan Matula Sep 04 '23 at 17:28
  • This DFA will accept 001 on state 2, so that breaks the even rule, I am thinking I need more states. – Sachihiro Sep 04 '23 at 17:36
  • Are you sure? It seems to me that 001 would leave the machine on state 3: 1 --0-> 2 --0-> 1 --1-> 3. – Jan Matula Sep 04 '23 at 17:43
  • Yes, you are correct – Sachihiro Sep 05 '23 at 09:07