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!

## show regularity,without the use of a dfa

**Moderators:** phlip, Moderators General, Prelates

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

A language is regular :<=> there exists a regular grammar that produces the language

Can you find such a grammar?

### 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**Location:**The Googleplex-
**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)))

- Quizatzhaderac
**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.

### Who is online

Users browsing this forum: No registered users and 7 guests