Question

Define a Turing machine TM3 that decides language L3 = { w | w ∈ Σ*, #_a(w) = #_b(w) } over the alphabet Σ = {a, b}.

IMPLEMENT USING JFLAP NO PAPER SOLUTION

Answer 1

We know that JFLAP defines a Turing Machine M as the septuple M = (Q, Σ, Γ, δ, qs, □, F) where

● Q is the set of internal states {qi | i is a nonnegative integer}

● Σ is the input alphabet

● Γ is the finite set of symbols in the tape alphabet ● δ : Q × Γ → Q × Γ × {L,R} is the transition function

● □ is the blank symbol.

● qs (is member of Q) is the initial state

● F (is a subset of Q) is the set of final state

One approach to defining this Turing Machine (TM) takes advantage of the existence of a single symbol, c, marking the end of the first occurrence of w and the beginning of the second occurrence of w. The TM can determine if the initial symbol and the first symbol following c are identical. If so, they can be removed from further consideration and each subsequent character checked for a match. If the symbols are ever different, the string is not in language L. If the symbol c is reached before the end of the input string, then the string is not in language L. If the end of string is reached before c, then the string is not in language L. Otherwise, because all symbols have been matched and the c symbol marks the exact center of the string, the string is in language L

Let me know if you have any doubts or if you need anything to change. 

If you are satisfied with the solution, please leave a +ve feedback : ) Let me know for any help with any other questions.

Thank You!
===========================================================================