HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
acceptsmidlanglerangletextrbracefordecidabilitysomelbrace

Problem

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?

Solution

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.

Context

StackExchange Computer Science Q#19171, answer score: 6

Revisions (0)

No revisions yet.