# How would a Turing Machine recognize n consecutive characters

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.

• 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? – Dániel Somogyi Jun 3 '18 at 21:02
• α 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". – Marin Tudor Jun 4 '18 at 15:36
• 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. – David Richerby Sep 1 '18 at 21:17

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.

• 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 – Marin Tudor Jun 3 '18 at 10:55