0
$\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?

$\endgroup$
4
  • $\begingroup$ cstheory is the wrong site for this question. Try cs instead. $\endgroup$ Dec 21, 2013 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, 2013 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$ Dec 29, 2013 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$ Dec 29, 2013 at 19:58

1 Answer 1

-1
$\begingroup$

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$.

$\endgroup$
3
  • $\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$ Dec 21, 2013 at 2:00
  • $\begingroup$ @templatetypedef The question was not whether the DFA accepts any input, but wether it accepts a given input. $\endgroup$ Dec 21, 2013 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$ Dec 21, 2013 at 2:16

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