## show regularity,without the use of a dfa

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

evinda
Posts: 32
Joined: Fri May 03, 2013 10:16 pm UTC

### show regularity,without the use of a dfa

Hey!
How can I show ,without the use of a DFA,that the language L={w:w in {1,2,4,5,7,9}*, w as a decimal gets divided completely by 7} is regular?

korona
Posts: 495
Joined: Sun Jul 04, 2010 8:40 pm UTC

### Re: show regularity,without the use of a dfa

How is regular defined? One definition is:
A language is regular :<=> there exists a regular grammar that produces the language
Can you find such a grammar?

evinda
Posts: 32
Joined: Fri May 03, 2013 10:16 pm UTC

### Re: show regularity,without the use of a dfa

korona wrote:How is regular defined? One definition is:
A language is regular :<=> there exists a regular grammar that produces the language
Can you find such a grammar?

I am facing difficulties,finding a grammar or expession.If the word should be divisible by 5,it would be (1|2|4|5|7|9)*5 ,but what happens when it should be divisible by 7?I have found this methodology:
To determine if a number is divisible by 7, take the last digit off the number, double it and subtract the doubled number from the remaining number. If the result is evenly divisible by 7 (e.g. 14, 7, 0, -7, etc.), then the number is divisible by seven. This may need to be repeated several times.

Could I use this to find a grammar??

Xanthir
My HERO!!!
Posts: 5426
Joined: Tue Feb 20, 2007 12:49 am UTC
Contact:

### Re: show regularity,without the use of a dfa

Are you familiar with how to build a DFA that tests if a number is divisible by 3? Can you turn that into an argument that doesn't directly use a DFA? If so, you should be able to do something similar with your language.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

Posts: 1821
Joined: Sun Oct 19, 2008 5:28 pm UTC
Location: Space Florida

### Re: show regularity,without the use of a dfa

Hint: mod 7 arithmetic.
The thing about recursion problems is that they tend to contain other recursion problems.