2

I only have one letter available as a language (e.g.: x). If I now enter "xxx" or "xxxxx" then the machine should accept this input because in the former case the length is 3 and in the second the length of the input is 5. And since the length should be divisible by 3 or 5, this should be accepted.

However, after hours of thinking, I can't find the solution. Can someone help me please?

I have tried the following: q0, q1, q2, q3, q4 and q5 --> each for the rest.

q3 and q5 would be my final states, since the remainder is 0 (divisible)

Then I can enter the following transitions:

 q0 --> q1 q1 --> q2 q2 --> q3 q3 --> q4 q4 --> q5 q5 --> q6

For example, if I have 6 "x" i.e. "xxxxxx" then I end up in state q0. So it has to be an accepting one too.

If I have 10 "x", i.e. "xxxxxxxxxx" I end up on q4. With 11 "x" I end up at q5, which is an accepting state which is not possible.

No matter how I spin it, I keep running into problems like this. Why am I thinking so wrongly here :-S

Improve this question
11
  • 1
    You know how to make an automaton that accepts strings of length multiple of 3, and you know how to make an automaton that accepts strings of length multiple of 5. Now you're looking for an automaton that accepts strings of length multiple of 3 and strings of length multiple of 5. This is the automaton for the union of two languages for which you have an automaton. This can be achieved by a kind of "cross-product" of automatons. Commented Oct 12, 2023 at 17:06
  • 1
    TL;DR: try with 15 states Commented Oct 12, 2023 at 17:08
  • 1
    Bonus question: if you're asked a similar question but with 4 and 6 instead of 3 and 5, how many states would you need? Commented Oct 12, 2023 at 17:14
  • 1
    really? Try it. I don't think it can be done with just 6 states (although proving that something is impossible is much harder than proving that something is possible) Commented Oct 12, 2023 at 17:21
  • 1
    I said 4 and 6, not 2 and 6. Yes you are correct, if it had been 2 and 6, then 6 states would be enough. In fact 2 states would have been enough!! Commented Oct 12, 2023 at 17:26

1 Answer 1

Reset to default
0

If you need to validate both multiples of n and m, start by just writing out every possible state until things repeat, which would be n x m states. So for n=3 and m=5:

S 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Then you mark terminals:

 S 1 2 (3) 4 (5) (6) 7 8 (9) (10) 11 (12) 13 14 (15)

And then you optimize by removing irrelevant nodes. For example, we don't need to visit 7, and then 8, just to get to 9, we can remove 8 and instead make the path from the non-terminal 7 to the terminal (9) consume two tokens. If we don't have that many tokens to consume, the DFA halts in a non-terminal state.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.