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

Postby evinda » Sun Jan 26, 2014 2:11 pm UTC

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?
Thanks in advance!

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

Re: show regularity,without the use of a dfa

Postby korona » Sun Jan 26, 2014 2:46 pm UTC

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

Postby evinda » Sun Jan 26, 2014 3:16 pm UTC

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??

User avatar
Xanthir
My HERO!!!
Posts: 5426
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: show regularity,without the use of a dfa

Postby Xanthir » Sun Jan 26, 2014 11:10 pm UTC

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)))

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

Re: show regularity,without the use of a dfa

Postby Quizatzhaderac » Wed Jan 29, 2014 8:33 pm UTC

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


Return to “Computer Science”

Who is online

Users browsing this forum: No registered users and 7 guests