# Decidability of $\lbrace \langle D \rangle \mid \text{$D$accepts$a^kb^k$for some$k > 0$}\rbrace$

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?

• 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$. Dec 21, 2013 at 6:00

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.
• 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. Dec 21, 2013 at 15:49
• 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). Dec 21, 2013 at 21:06
• 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. Dec 22, 2013 at 1:19
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.)