Timeline for Prove the language of numbers divisible by 3 is not regular using pumping lemma
Current License: CC BY-SA 4.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 8, 2020 at 6:47 | history | edited | John L. | CC BY-SA 4.0 |
More descriptive title
|
| May 21, 2015 at 0:45 | comment | added | Hendrik Jan | I am always very happy for an occasion to plug my own solution for binary numbers modulo three. As babou notes, neither 2, 10 nor 3 are essential in the construction. | |
| May 20, 2015 at 21:32 | comment | added | babou | @Danny The automaton is slightly easier to write in the case of 3 because of the property you rightly state in your comment. However, the way to design the automaton is essentially the same independently of the chosen divider. You could replace 3 by any integer $n$ and the construction of the automaton would still work, with $n$ states, of course. It is only that defining each transition would require a bit (more) of very elementary arithmetics. | |
| May 20, 2015 at 21:20 | comment | added | babou | IMHO there is no reason to downvote this question. If the OP understood the issue, he would not be asking,. So making errors is natural. At least he tried to make progress, and he is reporting it as expected. | |
| May 20, 2015 at 17:17 | review | Close votes | |||
| May 25, 2015 at 3:37 | |||||
| May 20, 2015 at 17:02 | comment | added | D.W.♦ | possible duplicate of How to prove that a language is not regular? | |
| May 20, 2015 at 14:25 | history | edited | Raphael |
edited tags
|
|
| May 20, 2015 at 14:25 | comment | added | Raphael | Check our reference questions. | |
| May 20, 2015 at 14:23 | vote | accept | Buddy | ||
| May 20, 2015 at 13:29 | comment | added | Danny | The language is regular. Note that a decimal number is divisible by 3 if and only if the sum of the digits is divisible by 3. Cou can create an automaton with 3 states, where each state represents the current sum of digits modulo 3 while reading your decimal input. | |
| May 20, 2015 at 13:20 | history | edited | babou | CC BY-SA 3.0 |
tag
|
| May 20, 2015 at 13:15 | answer | added | babou | timeline score: 4 | |
| May 20, 2015 at 13:08 | history | undeleted | Buddy | ||
| May 20, 2015 at 13:07 | history | deleted | Buddy | via Vote | |
| May 20, 2015 at 12:49 | review | First posts | |||
| May 20, 2015 at 13:20 | |||||
| May 20, 2015 at 12:44 | history | asked | Buddy | CC BY-SA 3.0 |