4
$\begingroup$

I'm trying to understand decidable languages. In particular, I would like to show that $$B = \lbrace \langle D \rangle \mid \exists k \geq 0 \,.\,\text{DFA $D$ accepts $a^k b^k$}\rangle.$$ I don't quite understand the process of proving these. I know that $a^kb^k$ is not regular, so then no DFA accepts it. I also know that $A_{DFA}$ (acceptance DFA) is decidable, I also know several other decidable languages like $E_{DFA}$ and $EQ_{DFA}$. How can I use these to prove that $B$ is decidable?

If no DFA accepts $a^kb^k$, doesn't that mean that $A_{DFA}$ will reject? So if $A_{DFA}$ rejects then shouldn't the decider for $B$ accept?

|cite|improve this question
$\endgroup$
  • 3
    $\begingroup$ It's not true that no DFA accepts all the words of the form $a^k b^k$. For example, a DFA with a single, accepting state accepts all inputs, and in particular all words of the form $a^k b^k$. What is true is that no DFA accepts exactly words of the form $a^k b^k$. $\endgroup$ – Yuval Filmus Dec 21 '13 at 6:00
6
$\begingroup$

Hint: Let $s_0$ be the starting state, $F$ the set of accepting states, and $q$ the transition function. The mapping $k \mapsto q(s_0,a^k)$ is eventually periodic and can be determined explicitly. The predicate $(s,k) \mapsto q(s,b^k) \in F$ is eventually periodic and can be determined explicitly. So the predicate $k \mapsto q(q(s_0,a^k),b^k) \in F$ is eventually periodic and can be determined explicitly.

Similarly, you can check whether a DFA accepts some word of the form $a^k b^k c^k$. The fact that the languages $\{ a^k b^k \mid k \in \mathbb{N} \}$ and $\{ a^k b^k c^k \mid k \in \mathbb{N} \}$ are not regular doesn't play any role here.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ So then could I construct another DFA $M$, that accepts the language $L(D)\cap L(D_{1})$, where $L(D_{1})$ is the language without $a^kb^k$. Then run $M$ on the $Empty_{DFA}$, if it accepts accept and if it rejects reject. $\endgroup$ – Data Dec 21 '13 at 15:49
  • 1
    $\begingroup$ This approach is problematic since $\{a^k b^k \mid k \in \mathbb{N}\}$ is accepted by no DFA. I'm not sure what you mean by "$L(D_1)$ is the language without $a^kb^k$", but if you mean $L(D) \setminus \{a^kb^k \mid k \in \mathbb{N}\}$, then this is not necessarily regular (for example, if $L(D) = \Sigma^*$ then it's not regular). $\endgroup$ – Yuval Filmus Dec 21 '13 at 21:06
  • $\begingroup$ I see. How about if I construct a CFG $G$ for $\{a^k b^k \mid k \in \mathbb{N}\}$, then I can construct another CFG $G'$ such that $L(G')=L(G)\cap L(D)$ (which should be possible bcs CFLs are closed under intersect with a regular language). Then run $G'$ on $Empty_{CFG}$, if it accepts reject, if it rejects accept. $\endgroup$ – Data Dec 22 '13 at 1:19
  • $\begingroup$ This points at D.W.'s answer, though as I mention, there is an approach which works even for some languages which are not context-free. $\endgroup$ – Yuval Filmus Dec 22 '13 at 5:30
  • 2
    $\begingroup$ @yuval-filmus You are absolutely right and your approach is much more powerful. For a systematic approach of this type of problem, see O. Carton and W. Thomas, The monadic theory of morphic infinite words and generalizations, Inform. Comput., vol. 176, pp. 51-76, 2002. $\endgroup$ – J.-E. Pin Dec 29 '13 at 11:52
3
$\begingroup$

Hint. The language $\{a^k b^k \mid k \in \mathbb{N}\}$ is context-free. So, can you construct a context-free grammar or pushdown automaton for it? What do you know about the closure properties of context-free languages and regular langauges? If you take the _____ of a regular language and a context-free language, what do you get? Do you know how to test whether a context-free language is _____? How does that help? (You fill in the blanks; to avoid giving too much away, I've left some blanks for you to fill in.)

|cite|improve this answer
$\endgroup$

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.