2
$\begingroup$

I have difficulties understanding how a TM could count number of characters. I have this problem where the input is made out of characters $\{a, b\}$ and I need to accept if there are $n$ characters of type a in the string. The formal definition for the input language is:

$$ L=\{ \{w,n\}\in\{a,b\}^*\times \mathbb{N} \mid n\neq 0, \exists \alpha,\beta\in\{a,b\} \text{ s.t. }w=\alpha a^n\beta\}. $$

What I do not understand is how could I hold the count since I need to have exactly n characters.

Improve this question
$\endgroup$
3
  • $\begingroup$ Just to clarify your question; are $\alpha{}$ and $\beta{}$ only one character? This means you accept only words of length n+2. Or do you want to accept any word, where n consecutive a's exist? $\endgroup$
    – Dániel Somogyi
    Commented Jun 3, 2018 at 21:02
  • $\begingroup$ α and β are any group of characters belonging to {a, b} that come before and after the sequence of n "a" characters. So it's not n + 2 length. Basically it can be rezumed to accepting a word that contains a sequence of exactly n characters "a". $\endgroup$
    – Marin Tudor
    Commented Jun 4, 2018 at 15:36
  • 7
    $\begingroup$ I don't understand your question. Languages are sets of strings, but the thing you define is a set of sets, where each set contains a string and a natural number. How are you coding that as a string so that you can present it as input to aTuring machine. Also, your comment says that $\alpha$ and $\beta$ are genreal strings but your problem statemnet says that they're single characters. $\endgroup$
    – David Richerby
    Commented Sep 1, 2018 at 21:17

1 Answer 1

Reset to default
0
$\begingroup$

What answer I came up with would be this. We would use a TM with 2 tapes, t1, t2 and 2 headers h1, h2.

  • P0. Scan the first tape with the input, if a character ∉ {a, b} REJECT.
  • P1. Write "#" and n character of "1" on t2, the head remaining in the right extremity.
  • P2. Read characters on t1 and while they are "a" repeat P3, P4.
  • P3. Move h1 to the right
  • P4. Read the character on t2 and if it's "1" move h2 to the left, if it's "#" move h2 to the right extremity.
  • P5. If the read character on t1 is "b" repeat P6
  • P6. Read the character on t2, if it's "1" move h2 to the right extremity, if it's "#" ACCEPT
  • P7. Getting at the end and not accepting means we REJECT

I had no example so I am not sure this is 100% correct but it's what I came up with after few hours of thinking. Hope it helps someone and please correct me if it's wrong.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Looking closely this does not account for the fact that I could have 2n+1 characters "a" followed by a "b" and it woukd accept it. Example: n = 3 , w = a a a a a a a b $\endgroup$
    – Marin Tudor
    Commented Jun 3, 2018 at 10:55

Your Answer

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

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