1
$\begingroup$

I am trying to solve this particular problem from Automata Theory by Ullman, Hopcroft, it is as shown below:

Let $A$ be a $DFA$ and $a$ be a particular input symbol of $A$, such that for all states $q$ of $A$ we have $\delta(q,a)=q$.

Show that either $\left\{a\right\}^*\subseteq L(A)$ or $\left\{a\right\}^*\cap L(A)=\emptyset$.

As far as my understanding of the first part of the problem, the language accepted by $A$ is $L(A)=\left\{a, aa, aaa, aaaa, aaaa...\right\}$.

Since, $\left\{a\right\}^*$ represents strings that belong to $L(A)$ including $\varepsilon$, therefore $\left\{a\right\}^*\subseteq L(A)$ is true.

How to show that $\left\{a\right\}^*\cap L(A)=\emptyset$? Doesn't $L(A)$ represent strings generated by $\left\{a\right\}^*$? How can the intersection be $\emptyset$?

$\endgroup$
0

1 Answer 1

1
$\begingroup$

Hint: Suppose that $a^k \in L(A)$ for some integer $k$. Consider the initial state $s$ of $A$. From the premises it follows that $\delta(s,a^k) = s$, and since $a^k \in L(A)$, $s$ must be an accepting state. For every integer $\ell$ we have $\delta(s,a^\ell) = s$ and so $a^\ell \in L(A)$.

$\endgroup$
6
  • $\begingroup$ Your answer is for the first part of the problem right? How and why is the intersection of $\left\{a\right\}^*\cap L(A)=\phi$? $\endgroup$ Commented Sep 27, 2014 at 20:23
  • $\begingroup$ As far as I understand the problem has only one part, and my hint shows you how to solve the entire problem. If you can't see why, I suggest you keep thinking. $\endgroup$ Commented Sep 27, 2014 at 20:25
  • $\begingroup$ Is it because $a^*$ produces $\varepsilon$ which is not a member of $L(A)$? And hence $\left\{\varepsilon\right\}\cap L(A)=\phi$ $\endgroup$ Commented Sep 27, 2014 at 20:27
  • $\begingroup$ My argument shows that if $a^k \in L(A)$ for some $k$ then $a^k \in L(A)$ for all $k$. This implies your problem. $\endgroup$ Commented Sep 27, 2014 at 20:28
  • $\begingroup$ I'm sorry I'm being a noob here but I've been thinking over this problem for 2 days straight! Can you please explain it to me in layman terms? I'm unable to see what I'm missing here. $\endgroup$ Commented Sep 27, 2014 at 20:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.