# Is the language regular?

#### evinda

##### Well-known member
MHB Site Helper
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?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
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

##### Well-known member
MHB Site Helper
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? #### Klaas van Aarsen

##### MHB Seeker
Staff member
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

##### Well-known member
MHB Site Helper
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?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
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.

#### Klaas van Aarsen

##### MHB Seeker
Staff member
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

##### Well-known member
MHB Site Helper
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  Is it right?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
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!! 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

##### Well-known member
MHB Site Helper
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. 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

##### Well-known member
MHB Site Helper
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? #### Klaas van Aarsen

##### MHB Seeker
Staff member
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

##### Well-known member
MHB Site Helper
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

##### Well-known member
MHB Site Helper
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

##### Well-known member
MHB Site Helper
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? #### Klaas van Aarsen

##### MHB Seeker
Staff member
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

##### Well-known member
MHB Site Helper
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

##### Well-known member
MHB Math Scholar
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

##### Well-known member
MHB Site Helper
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?  #### Klaas van Aarsen

##### MHB Seeker
Staff member
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! #### evinda

##### Well-known member
MHB Site Helper
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! 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? #### Klaas van Aarsen

##### MHB Seeker
Staff member
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$$

Last edited:

#### evinda

##### Well-known member
MHB Site Helper
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!!!! #### Klaas van Aarsen

##### MHB Seeker
Staff member
I understand..Thanks a lot!!!! Oops. Forgot the terminal state. Just added it in my previous post.

#### evinda

##### Well-known member
MHB Site Helper
Oops. Forgot the terminal state. Just added it in my previous post.
Oh yes,right!!! Thank you very much!!! 