0
$\begingroup$

I'm working on a problem that asks for an informal description of a deterministic Turing Machine (TM) for the following language:

$L=\{a^i b^j a^k b^l | i+j=k+l\}$

The challenge is to describe how a deterministic TM would accept strings in this language, ensuring the condition i+j=k+l holds. How should I approach designing a deterministic TM for this language? What would be a good informal description of the steps the TM should take? Any guidance on this would be greatly appreciated!

Improve this question
$\endgroup$
8
  • $\begingroup$ You can build a PDA for the language then construct the TM adapted from the PDA. $\endgroup$
    – minh quý lê
    Commented Nov 3 at 8:19
  • $\begingroup$ Thank you for your response. How would i construct a PDA for this language ? $\endgroup$
    – Fred
    Commented Nov 3 at 9:45
  • $\begingroup$ I recommend to start with cases that look hard. With a word like $a^8b^6$, a nondeterministic machine correctly has $j=0$. $\endgroup$
    – greybeard
    Commented Nov 3 at 11:46
  • $\begingroup$ @greybeard We should treat this nondeterministically. $\endgroup$
    – minh quý lê
    Commented Nov 3 at 12:40
  • $\begingroup$ @greybeard I mean we could built a nondeterministic PDA for $L$ to treat your case $jk=0$. Then we base on CYK algorithm to construct a polynomial time TM, $CFL\subseteq P$. I have yet to succeed in finding a way to construct a deterministic PDA. $\endgroup$
    – minh quý lê
    Commented Nov 3 at 17:16

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.