- Thread starter
- #1

- Apr 13, 2013

- 3,740

I have a question.Given $\Sigma=\{1,2,4,5,7,9\}$ and $L=\{w:w \in \Sigma^{*},\text{ and w as a decimal gets divided completely by } 7\}$,is the language L regular?

- Thread starter evinda
- Start date

- Thread starter
- #1

- Apr 13, 2013

- 3,740

I have a question.Given $\Sigma=\{1,2,4,5,7,9\}$ and $L=\{w:w \in \Sigma^{*},\text{ and w as a decimal gets divided completely by } 7\}$,is the language L regular?

- Admin
- #2

- Mar 5, 2012

- 9,143

Hi!!!

I have a question.Given $\Sigma=\{1,2,4,5,7,9\}$ and $L=\{w:w \in \Sigma^{*},\text{ and w as a decimal gets divided completely by } 7\}$,is the language L regular?

Did you try anything?

Which methods could be applied?

Does any method lead to anything?

- Thread starter
- #3

- Apr 13, 2013

- 3,740

I thought that I could show that the language is regular,drawing a DFA,which states are all the possible remainders..Is this right?Hi!!!

Did you try anything?

Which methods could be applied?

Does any method lead to anything?

Could I also do this,without the use of a DFA?

- Admin
- #4

- Mar 5, 2012

- 9,143

That was also my first idea.I thought that I could show that the language is regular,drawing a DFA,which states are all the possible remainders..Is this right?

Could I also do this,without the use of a DFA?

I guess you could also create a regular expression, but I think that would be more complicated.

- Thread starter
- #5

- Apr 13, 2013

- 3,740

I just can imagine that the final state of the DFA should be the one with $\text{remainder}=0$,but I don't really know which other transitions there could be..That was also my first idea.

I guess you could also create a regular expression, but I think that would be more complicated.

Also,could you help me to construct the regular expression?

- Admin
- #6

- Mar 5, 2012

- 9,143

Each transition would correspond to the next digit on the input.I just can imagine that the final state of the DFA should be the one with $\text{remainder}=0$,but I don't really know which other transitions there could be..

Also,could you help me to construct the regular expression?

Each state would correspond to a remainder...

Best regular expression I can come up with at this time is:

77* | 14 | 21 | 4(2|9) | 91 | 11(2|9) | ...

But this is not a finite regular expression.

Hmm, perhaps if we continue a couple more steps we'll see a pattern emerge that we can make more concise.

- Admin
- #7

- Mar 5, 2012

- 9,143

This state would also be the final state, since we would have a number that is divisible by 7.

Then, after an 1, we can go to the state with remainder 1.

From state 1, a 2 would bring us for instance to the number 12, which has remainder 5.

So a 2 would bring us from state 1 to state 5.

Perhaps you can draw something?

- Thread starter
- #8

- Apr 13, 2013

- 3,740

I have tried to draw the DFA.I hope you can distinguish what I have written

This state would also be the final state, since we would have a number that is divisible by 7.

Then, after an 1, we can go to the state with remainder 1.

From state 1, a 2 would bring us for instance to the number 12, which has remainder 5.

So a 2 would bring us from state 1 to state 5.

Perhaps you can draw something?

Is it right?

- Admin
- #9

- Mar 5, 2012

- 9,143

Aha!I have tried to draw the DFA.I hope you can distinguish what I have written

View attachment 1866

Is it right?

I like the colors!!

Looks good... except for that arrow from 4 to 1 that has a 3 attached to it.

I believe 3 is not part of the alphabet.

- Thread starter
- #10

- Apr 13, 2013

- 3,740

I understand... thank you very much!!!Aha!

I like the colors!!

Looks good... except for that arrow from 4 to 1 that has a 3 attached to it.

I believe 3 is not part of the alphabet.

- - - Updated - - -

Could you also explain me how I can find the regular expression??Best regular expression I can come up with at this time is:

77* | 14 | 21 | 4(2|9) | 91 | 11(2|9) | ...

But this is not a finite regular expression.

Hmm, perhaps if we continue a couple more steps we'll see a pattern emerge that we can make more concise.

- Thread starter
- #11

- Apr 13, 2013

- 3,740

I am looking again at the exercise..and I have also an other question...What is meant with the fact that $w$ is a decimal?I understand... thank you very much!!!

- - - Updated - - -

Could you also explain me how I can find the regular expression??

- Admin
- #12

- Mar 5, 2012

- 9,143

I don't see how we can find a finite regular expression.Could you also explain me how I can find the regular expression??

That means that $w$ is supposed to be interpreted as a number consisting of digits between $0$ and $9$ (decimal means base-10), even though the symbols in the alphabet are only 1,2,4,5,7,9.I am looking again at the exercise..and I have also an other question...What is meant with the fact that $w$ is a decimal?

So it's

- Thread starter
- #13

- Apr 13, 2013

- 3,740

Never mind!I don't see how we can find a finite regular expression.

I understand..Thank you very much for your help!!!!That means that $w$ is supposed to be interpreted as a number consisting of digits between $0$ and $9$ (decimal means base-10), even though the symbols in the alphabet are only 1,2,4,5,7,9.

So it'snotfor instance an octal (base-8) or hexadecimal number (base-16).

- Thread starter
- #14

- Apr 13, 2013

- 3,740

I am trying to find also a regular expression..but which identity should have a number so that is gets divided completely by 7?I guess you could also create a regular expression, but I think that would be more complicated.

- Thread starter
- #15

- Apr 13, 2013

- 3,740

I thought that it could be $(1|2|4|5|7|9)^{*}7$ but then I found a counterexample.. $419$ is not divisible by 7!! Is it maybe similar to this one?Do I just have to change something or is it completely wrong?I am trying to find also a regular expression..but which identity should have a number so that is gets divided completely by 7?

- Admin
- #16

- Mar 5, 2012

- 9,143

I am trying to find also a regular expression..but which identity should have a number so that is gets divided completely by 7?

I am pretty sure that it cannot be done.I thought that it could be $(1|2|4|5|7|9)^{*}7$ but then I found a counterexample.. $419$ is not divisible by 7!! Is it maybe similar to this one?Do I just have to change something or is it completely wrong?

If only it was about divisibility by 5 for instance. That's easy. It needs to end in either 0 or 5.

But with 7 any sequence of digits is fine with basically no clear cue what the last digit should be.

Ah well, to be fair, there is a pattern (google it), but I don't think it can be caught in a regular expression.

- Thread starter
- #17

- Apr 13, 2013

- 3,740

Ok,I understand.. And something else..Could I just write the function of the PDA, instead of drawing it?I am pretty sure that it cannot be done.

If only it was about divisibility by 5 for instance. That's easy. It needs to end in either 0 or 5.

But with 7 any sequence of digits is fine with basically no clear cue what the last digit should be.

Ah well, to be fair, there is a pattern (google it), but I don't think it can be caught in a regular expression.

- Jan 30, 2012

- 2,516

How can this be if there is a supposedly correct finite automaton in post #8?I don't see how we can find a finite regular expression.

This page on Stack Overflow explains the idea behind the automaton. The transition function is the following (the first argument is a state, the second one is a new symbol read).

\[

\delta(q,s)=(10q+s)\text{ mod }7

\]

I have not checked everything, but the transitions from 2 seem correct except for symbol 1, which should lead to state 0.

The standard algorithm for converting a DFA into a regular expression may return expressions that are exponential in size compared to the size of the automaton. Here you can find an explicit regular expression whose length is 12 or 13 thousand, as well as the automaton.

- Thread starter
- #19

- Apr 13, 2013

- 3,740

Could I find maybe a simpler grammar or isn't it possible?How can this be if there is a supposedly correct finite automaton in post #8?

This page on Stack Overflow explains the idea behind the automaton. The transition function is the following (the first argument is a state, the second one is a new symbol read).

\[

\delta(q,s)=(10q+s)\text{ mod }7

\]

I have not checked everything, but the transitions from 2 seem correct except for symbol 1, which should lead to state 0.

The standard algorithm for converting a DFA into a regular expression may return expressions that are exponential in size compared to the size of the automaton. Here you can find an explicit regular expression whose length is 12 or 13 thousand, as well as the automaton.

- Admin
- #20

- Mar 5, 2012

- 9,143

The transition function is the following (the first argument is a state, the second one is a new symbol read).

\[

\delta(q,s)=(10q+s)\text{ mod }7

\]

ThatCould I find maybe a simpler grammar or isn't it possible?

Augment it with a definition of the input symbols, the set of states, the initial state, the set of final states, and there you go!

- Thread starter
- #21

- Apr 13, 2013

- 3,740

I tried this:Thatisthe simpler grammar in the form of a deterministic finite state machine. The $\delta$ function describes the set of transitions.

Augment it with a definition of the input symbols, the set of states, the initial state, the set of final states, and there you go!

-input-symbols: $\Sigma=\{1,2,4,5,7,9\}$

-set of states: $\Sigma_{k}=\{0,1,2,3,4,5,6\}$

-initial state: $I=\{0\}$

-set of final states: $F=\{0\}$

-transition: $\delta(q,s)=(10q+s)mod7$

But...isn't it the description of the DFA ?What do you mean that it is a grammar?

- Admin
- #22

- Mar 5, 2012

- 9,143

I tend to mix them up, although I guess formally a DFA is not a grammar.I tried this:

-input-symbols: $\Sigma=\{1,2,4,5,7,9\}$

-set of states: $\Sigma_{k}=\{0,1,2,3,4,5,6\}$

-initial state: $I=\{0\}$

-set of final states: $F=\{0\}$

-transition: $\delta(q,s)=(10q+s)mod7$

But...isn't it the description of the DFA ?What do you mean that it is a grammar?

Anyway, it is straight forward to convert the DFA to a set of production rules.

$$S_0 \to 1\ S_1\ |\ 2\ S_2\ |\ ...$$

$$S_1 \to ...$$

In other words, the grammar $G = (N, \Sigma, P, S)$ with

$$N = \{S_0,S_1,S_2,S_3,S_4,S_5,S_6\}$$

$$\Sigma = \{1,2,4,5,7,9\}$$

$$P = \{ S_q \to s S_{(10q+s)\text{mod}7} : s \in \Sigma, S_q \in N \} \cup \{ S_0 \to \varnothing \}$$

$$S = S_0$$

Last edited:

- Thread starter
- #23

- Apr 13, 2013

- 3,740

I understand..Thanks a lot!!!!I tend to mix them up, although I guess formally a DFA is not a grammar.

Anyway, it is straight forward to convert the DFA to a set of production rules.

$$S_0 \to 1\ S_1\ |\ 2\ S_2\ |\ ...$$

$$S_1 \to ...$$

In other words, the grammar $G = (N, \Sigma, P, S)$ with

$$N = \{S_0,S_1,S_2,S_3,S_4,S_5,S_6\}$$

$$\Sigma = \{1,2,4,5,7,9\}$$

$$P = \{ S_q \to s S_{(10q+s)\text{mod}7} : s \in \Sigma, S_q \in N \}$$

$$S = S_0$$

- Admin
- #24

- Mar 5, 2012

- 9,143

Oops. Forgot the terminal state.I understand..Thanks a lot!!!!

Just added it in my previous post.

- Thread starter
- #25

- Apr 13, 2013

- 3,740

Oh yes,right!!! Thank you very much!!!Oops. Forgot the terminal state.

Just added it in my previous post.