Regularity of Language L Over Decimal Divisibility by 7

[evinda]

Hello! :)
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?

 

[I like Serena]

Hello! :)
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?

Hi! ;)

Did you try anything?
Which methods could be applied?
Does any method lead to anything?

 

[evinda]

Hi! ;)

Did you try anything?
Which methods could be applied?
Does any method lead to anything?

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 like Serena]

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?

That was also my first idea.
I guess you could also create a regular expression, but I think that would be more complicated.

 

[evinda]

That was also my first idea.
I guess you could also create a regular expression, but I think that would be more complicated.

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?

 

[I like Serena]

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 transition would correspond to the next digit on the input.
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.

 

[I like Serena]

We can start at the state with remainder 0, corresponding to the empty symbol.
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?

 

[evinda]

We can start at the state with remainder 0, corresponding to the empty symbol.
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?

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

Is it right?

 

[I like Serena]

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

Is it right?

Aha!
I like the colors! (Cool)

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.

 

[evinda]

Aha!
I like the colors! (Cool)

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.

I understand... thank you very much! :)

- - - Updated - - -

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.

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

 

[evinda]

I understand... thank you very much! :)

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

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 like Serena]

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

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

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?

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's not for instance an octal (base-8) or hexadecimal number (base-16).

 

[evinda]

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

Never mind! :)

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's not for instance an octal (base-8) or hexadecimal number (base-16).

I understand..Thank you very much for your help!

 

[evinda]

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

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

 

[evinda]

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 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 like Serena]

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

 

[evinda]

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.

Ok,I understand.. :) And something else..Could I just write the function of the PDA, instead of drawing it?

 

[Evgeny.Makarov]

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

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.

 

[evinda]

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.

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

 

[I like Serena]

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
\]

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

That is the 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! (Cool)

 

[evinda]

That is the 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! (Cool)

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?

 

[I like Serena]

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?

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 \} \cup \{ S_0 \to \varnothing \}$$
$$S = S_0$$

 

[evinda]

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

I understand..Thanks a lot! :)

 

[I like Serena]

I understand..Thanks a lot! :)

Oops. Forgot the terminal state.
Just added it in my previous post.

 

[evinda]

Oops. Forgot the terminal state.
Just added it in my previous post.

Oh yes,right! Thank you very much!