832 views
7 votes
7 votes
Suppose $M = (Q, \Sigma, \delta, q_0, F)$ is a deterministic finite automaton, and suppose there exists a state $q \in Q$, a string $z \in \Sigma$, and integers $i, j > 0$ such that $\delta(q, z^i) = \delta(q, z^j) = q$. Prove that $\delta(q, z^{\gcd(i,j)}) = q.$

2 Answers

7 votes
7 votes

Consider the DFA for the language "strings which contains at least one $a$" over $\sum=\{a\}$

Here $q_2$ is final state

Consider a string $(q_2,a^8)=(q_2,a^{12})=q_2$

Now $(q_2, a^{\gcd(8,12)}) \Rightarrow (q_2, a^4)==q_2$

as $\gcd$ of $8,12$ is $4$

and $a^4$  also goes to $q_2$ hence proved

edited by
1 votes
1 votes
I'll try building formal proof let me know how it is.

Case 1: Both $i,j$ are prime(different) numbers: In that case $gcd(i,j)=1$ and hence $\delta(q,z)=q$

Given that $\delta(q,z^i)=\delta(q,z^j)=q$ for $i,j \gt 0$ is true.

Case 2: One of $i\,orj$ is prime and other one is a composite number. In this case $gcd(i,j)=i\,or\,j$ depending whether $i$ is prime or $j$ is prime.

Suppose it was like $gcd(i,j)=i$ then $\delta(q,z^i)=q$ holds as $\delta(q,z^i)=\delta(q,z^j)=q$ is true for $i,j \gt 0$

Case 3: Suppose both $i,j$ are composite numbers and let $gcd(i,j)=k$

given $\delta(q,z^i)=\delta(q,z^j)=q$ holds. I can re-write it as

$\delta(q,z^{i-k}.z^k)=\delta(q,z^{j-k}.z^k)=q$...(A) also holds. for some $z^k$

Using right-invariance property which states that if for two different strings $x,y$ if $\delta(q,x)=\delta(q,y)$, then for some string $z$ in the same input alphabet,$\delta(q,xz)=\delta(q,yz)$

So, by the same property

$\delta(q,z^{i-k})=\delta(q,z^{j-k})=q$

From result (A) it is not too hard to see that $\delta(q,z^k)=q$ where $k=gcd(i,j)$

Let me know if the proof is correct.

Related questions

12 votes
12 votes
3 answers
2
go_editor asked Jun 1, 2016
1,547 views
Write a regular expression for all strings of $0$’s and $1$’s in which the total number of $0$’s to the right of each $1$ is even. Justify your answer.
8 votes
8 votes
5 answers
3
go_editor asked May 31, 2016
1,877 views
Consider the following statement:$\text{ For all languages }L \subseteq \{0, 1\}^*, \text{ if }L^* \text{ is regular then L is regular.}$Is the above statement true? Just...
6 votes
6 votes
2 answers
4
go_editor asked Jun 3, 2016
929 views
Let $L$ be the set of strings over $\{0, 1\}$ containing an unequal number of $0$s and $1$s. Prove that$L$ is not regular.$L^2$ is regular.