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
$\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$
  • $\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$ – Siddharth Thevaril Sep 27 '14 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$ – Yuval Filmus Sep 27 '14 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$ – Siddharth Thevaril Sep 27 '14 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$ – Yuval Filmus Sep 27 '14 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$ – Siddharth Thevaril Sep 27 '14 at 20:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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