Welcome to our community

Be a part of something great, join today!

Is the language regular?

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,720
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
Mar 5, 2012
8,797
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
Apr 13, 2013
3,720
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? :confused:
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,797
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? :confused:
That was also my first idea. :cool:
I guess you could also create a regular expression, but I think that would be more complicated.
 

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,720
That was also my first idea. :cool:
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.. :confused:
Also,could you help me to construct the regular expression?
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,797
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.. :confused:
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
Mar 5, 2012
8,797
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? :eek:
 

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,720
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? :eek:
I have tried to draw the DFA.I hope you can distinguish what I have written :eek:
pda.jpg

Is it right?
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,797
I have tried to draw the DFA.I hope you can distinguish what I have written :eek:
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. :eek:
 

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,720
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. :eek:
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?? :confused:
 

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,720
I understand... thank you very much!!! :)

- - - Updated - - -



Could you also explain me how I can find the regular expression?? :confused:
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? :confused:
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,797
Could you also explain me how I can find the regular expression?? :confused:
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? :confused:
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
Apr 13, 2013
3,720
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!!!! :rolleyes:
 

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,720
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
Apr 13, 2013
3,720
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? :confused:
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,797
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? :confused:
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
Apr 13, 2013
3,720
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? :confused:
 

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,493
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
Apr 13, 2013
3,720
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? :eek: :confused:
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,797
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? :eek: :confused:
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

Well-known member
MHB Site Helper
Apr 13, 2013
3,720
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? :confused:
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,797
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? :confused:
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
Apr 13, 2013
3,720
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
Mar 5, 2012
8,797

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,720