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?


marked as duplicate by D.W., Andrej Bauer, David Richerby, Juho, Yuval Filmus Dec 29 '13 at 11:42

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

migrated from stackoverflow.com Dec 29 '13 at 8:01

This question came from our site for professional and enthusiast programmers.

  • $\begingroup$ cstheory is the wrong site for this question. Try cs instead. $\endgroup$ – templatetypedef Dec 21 '13 at 2:45
  • 1
    $\begingroup$ Data, for future reference: please don't cross-post the same question on multiple StackExchange sites. That is prohibited by StackExchange rules. I see that you posted it simultaneously on both StackOverflow and on CS.SE. That causes duplication of effort by folks who answered the question without realizing others have already answered it, which is impolite to answerers; and it causes duplication of content on this site, which others have to clean up. If you ever discover you've posted your question to the wrong site, you can flag it for moderator attention and ask them to migrate it. $\endgroup$ – D.W. Dec 29 '13 at 8:26
  • $\begingroup$ Case in point: I just wasted my time editing this question, only to discover there was a duplicate with a good answer. And then I had to duplicate my effort. @D.W. is not making stuff up, you know. $\endgroup$ – Andrej Bauer Dec 29 '13 at 9:56
  • $\begingroup$ I originally posted the question on SE. It wasn't until the question was put on hold and I was made aware that CS.SE was the appropriate place for this question that I posted it here. I did not know the moderators would migrate it here,, now I know. I apologize for the mess. $\endgroup$ – Data Dec 29 '13 at 19:58

Corollary 3.19 from "An Introduction to the Theory of Computation": "A language is decidable if and only if some nondeterministic Turing machine decides it."

You can construct a nondeterministic Turing machine, $TM_A$, which is a decider for the language : $A_DFA = \lbrace \langle B,w \rangle \mid \text{$B$ is a DFA accepting $w$}\rangle$.

$TM_A$ works as follows on input $\langle B,w \rangle$, where $B$ is a DFA and $w$ is a string:

  1. Simulate $B$ on input $w$.
  2. If the simulation ends in an accept state, accept. If it ends in an non-accepting state, reject.

Update: The string $a^kb^k$ is not regular and cannot be accepted by a DFA. A CFG for that string would be something like : $A \to aAb \mid \varepsilon$.

  • $\begingroup$ How does the fact that A_DFA is decidable help you determine if the DFA accepts any string of the form a^k b^k? $\endgroup$ – templatetypedef Dec 21 '13 at 2:00
  • $\begingroup$ @templatetypedef The question was not whether the DFA accepts any input, but wether it accepts a given input. $\endgroup$ – Pétur Ingi Egilsson Dec 21 '13 at 2:07
  • 1
    $\begingroup$ @Pétur- There is no DFA that accepts precisely strings of the form a^k b^k, but there are many DFAs that accept some number of these strings or all of these strings plus some other strings. My interpretation of the question is "given a DFA, can you decide whether the DFA accepts any string of the form a^k b^k?" rather than "can you decide whether the DFA accepts all and only strings of the form a^k b^k?" $\endgroup$ – templatetypedef Dec 21 '13 at 2:16

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