### TM accepting strings with equal number of 0*s and 1*s

```TM accepting strings with equal
number of 0’s and 1’s
Thamer Al sulaiman
TM accepting strings with equal
number of 0’s and 1’s
• The Turing machine accepts strings such as:
001110, 1011.
• The Turing Machine rejects strings such as:
010, 11100 and so on.
Algorithm
A possible algorithm to solve this problem is:
• For each symbol: 0 (1) read from input tape, search for a
matching 1 (0), and replace both symbols with another
symbol (to ignore matched symbols in subsequent steps).
• If the respective symbol is not found – the end of the
string reached without matching symbol (which means
the string contains an unequal number of 0s and 1s),
then we reject.
• If all 0s and 1s are matched, then accept.
q
Δ/Δ,R
A
0/x,R
0/0,R
C
Δ/Δ,R
1/x,R
x/x,R
Δ/Δ,R
R
1/x,L
Δ/Δ,R
B
0/x,L
D
0/x,R
0/0,L
1/1,L
x/x,L
Δ/Δ,R
E
Δ/Δ,R
F
- q is the initial state,
- R is the rejection state,
- F is the acceptance state.
x/x,R
1/x,R
1/1,R
q
Δ/Δ,R
A
0/x,R
0/0,R
C
Δ/Δ,R
1/x,R
x/x,R
Δ/Δ,R
R
1/x,L
Δ/Δ,R
B
1/1,R
0/x,L
D
0/x,R
0/0,L
1/1,L
x/x,L
1/x,R
Δ/Δ,R
E
Δ/Δ,R
F
Input string: 001
x/x,R
q Δ001
q
Δ/Δ,R
A
0/x,R
0/0,R
C
Δ/Δ,R
1/x,R
x/x,R
Δ/Δ,R
R
1/x,L
Δ/Δ,R
B
1/1,R
0/x,L
D
0/x,R
0/0,L
1/1,L
x/x,L
Δ/Δ,R
E
Δ/Δ,R
F
1/x,R
Input string: 001
x/x,R
q Δ001 ⊢ ΔA001
q
Δ/Δ,R
A
0/x,R
0/0,R
C
Δ/Δ,R
1/x,R
x/x,R
Δ/Δ,R
R
1/x,L
Δ/Δ,R
B
1/1,R
0/x,L
D
0/x,R
0/0,L
1/1,L
x/x,L
Δ/Δ,R
E
Δ/Δ,R
F
1/x,R
Input string: 001
x/x,R
q Δ001 ⊢ ΔA001 ⊢ ΔxC01
q
Δ/Δ,R
A
0/x,R
0/0,R
C
Δ/Δ,R
1/x,R
x/x,R
Δ/Δ,R
R
1/x,L
Δ/Δ,R
B
1/1,R
0/x,L
D
0/x,R
0/0,L
1/1,L
x/x,L
Δ/Δ,R
E
Δ/Δ,R
F
1/x,R
Input string: 001
x/x,R
q Δ001 ⊢ ΔA001 ⊢ ΔxC01 ⊢ Δx0C1
q
Δ/Δ,R
A
0/x,R
0/0,R
C
Δ/Δ,R
1/x,R
x/x,R
Δ/Δ,R
R
1/x,L
Δ/Δ,R
B
1/1,R
0/x,L
D
0/x,R
0/0,L
1/1,L
x/x,L
Δ/Δ,R
E
Δ/Δ,R
F
1/x,R
Input string: 001
x/x,R
q Δ001 ⊢ ΔA001 ⊢ ΔxC01 ⊢ Δx0C1
⊢ ΔxD0x
q
Δ/Δ,R
A
0/x,R
0/0,R
C
Δ/Δ,R
1/x,R
x/x,R
Δ/Δ,R
R
1/x,L
Δ/Δ,R
B
1/1,R
0/x,L
D
0/x,R
0/0,L
1/1,L
x/x,L
Δ/Δ,R
E
Δ/Δ,R
F
1/x,R
Input string: 001
x/x,R
q Δ001 ⊢ ΔA001 ⊢ ΔxC01 ⊢ Δx0C1
⊢ ΔxD0x ⊢ ΔDx0x
q
Δ/Δ,R
A
0/x,R
0/0,R
C
Δ/Δ,R
1/x,R
x/x,R
Δ/Δ,R
R
1/x,L
Δ/Δ,R
B
1/1,R
0/x,L
D
0/x,R
0/0,L
1/1,L
x/x,L
Δ/Δ,R
E
Δ/Δ,R
F
1/x,R
Input string: 001
x/x,R
q Δ001 ⊢ ΔA001 ⊢ ΔxC01 ⊢ Δx0C1
⊢ ΔxD0x ⊢ ΔDx0x ⊢ DΔx0x
q
Δ/Δ,R
A
0/x,R
0/0,R
C
Δ/Δ,R
1/x,R
x/x,R
Δ/Δ,R
R
1/x,L
Δ/Δ,R
B
1/1,R
0/x,L
D
0/x,R
0/0,L
1/1,L
x/x,L
Δ/Δ,R
E
Δ/Δ,R
F
1/x,R
Input string: 001
x/x,R
q Δ001 ⊢ ΔA001 ⊢ ΔxC01 ⊢ Δx0C1
⊢ ΔxD0x ⊢ ΔDx0x ⊢ DΔx0x ⊢ ΔEx0x
q
Δ/Δ,R
A
0/x,R
0/0,R
C
Δ/Δ,R
1/x,R
x/x,R
Δ/Δ,R
R
1/x,L
Δ/Δ,R
B
1/1,R
0/x,L
D
0/x,R
0/0,L
1/1,L
x/x,L
Δ/Δ,R
E
Δ/Δ,R
F
1/x,R
Input string: 001
x/x,R
q Δ001 ⊢ ΔA001 ⊢ ΔxC01 ⊢ Δx0C1
⊢ ΔxD0x ⊢ ΔDx0x ⊢ DΔx0x ⊢ ΔEx0x
⊢ ΔxE0x
q
Δ/Δ,R
A
0/x,R
0/0,R
C
Δ/Δ,R
1/x,R
x/x,R
Δ/Δ,R
R
1/x,L
Δ/Δ,R
B
1/1,R
0/x,L
D
0/x,R
0/0,L
1/1,L
x/x,L
Δ/Δ,R
E
Δ/Δ,R
F
1/x,R
Input string: 001
x/x,R
q Δ001 ⊢ ΔA001 ⊢ ΔxC01 ⊢ Δx0C1
⊢ ΔxD0x ⊢ ΔDx0x ⊢ DΔx0x ⊢ ΔEx0x
⊢ ΔxE0x ⊢ ΔxxCx
q
Δ/Δ,R
A
0/x,R
0/0,R
C
Δ/Δ,R
1/x,R
x/x,R
Δ/Δ,R
R
1/x,L
Δ/Δ,R
B
1/1,R
0/x,L
D
0/x,R
0/0,L
1/1,L
x/x,L
Δ/Δ,R
E
Δ/Δ,R
F
1/x,R
Input string: 001
x/x,R
q Δ001 ⊢ ΔA001 ⊢ ΔxC01 ⊢ Δx0C1
⊢ ΔxD0x ⊢ ΔDx0x ⊢ DΔx0x ⊢ ΔEx0x
⊢ ΔxE0x ⊢ ΔxxCx ⊢ ΔxxxCΔ
q
Δ/Δ,R
A
0/x,R
0/0,R
C
Δ/Δ,R
1/x,R
x/x,R
Δ/Δ,R
R
1/x,L
Δ/Δ,R
B
1/1,R
0/x,L
D
0/x,R
0/0,L
1/1,L
x/x,L
Δ/Δ,R
E
Δ/Δ,R
F
1/x,R
Input string: 001
x/x,R
q Δ001 ⊢ ΔA001 ⊢ ΔxC01 ⊢ Δx0C1
⊢ ΔxD0x ⊢ ΔDx0x ⊢ DΔx0x ⊢ ΔEx0x
⊢ ΔxE0x ⊢ ΔxxCx ⊢ ΔxxxCΔ
⊢ R (reject)
q
Δ/Δ,R
A
0/x,R
0/0,R
C
Δ/Δ,R
1/x,R
x/x,R
Δ/Δ,R
R
1/x,L
Δ/Δ,R
B
1/1,R
0/x,L
D
0/x,R
0/0,L
1/1,L
x/x,L
Δ/Δ,R
E
Δ/Δ,R
F
1/x,R
Input string: 0101
q Δ0011
x/x,R
q
Δ/Δ,R
A
0/x,R
0/0,R
C
Δ/Δ,R
1/x,R
x/x,R
Δ/Δ,R
R
1/x,L
Δ/Δ,R
B
1/1,R
0/x,L
D
0/x,R
0/0,L
1/1,L
x/x,L
Δ/Δ,R
E
Δ/Δ,R
F
1/x,R
Input string: 0101
q Δ0011 ⊢ ΔA0101
x/x,R
q
Δ/Δ,R
A
0/x,R
0/0,R
C
Δ/Δ,R
1/x,R
x/x,R
Δ/Δ,R
R
1/x,L
Δ/Δ,R
B
1/1,R
0/x,L
D
0/x,R
0/0,L
1/1,L
x/x,L
Δ/Δ,R
E
Δ/Δ,R
F
1/x,R
Input string: 0101
q Δ0011 ⊢ ΔA0101 ⊢ ΔxC101
x/x,R
q
Δ/Δ,R
A
0/x,R
0/0,R
C
Δ/Δ,R
1/x,R
x/x,R
Δ/Δ,R
R
1/x,L
Δ/Δ,R
B
1/1,R
0/x,L
D
0/x,R
0/0,L
1/1,L
x/x,L
Δ/Δ,R
E
Δ/Δ,R
F
x/x,R
1/x,R
Input string: 0101
q Δ0011 ⊢ ΔA0101 ⊢ ΔxC101
⊢ ΔDxx01
q
Δ/Δ,R
A
0/x,R
0/0,R
C
Δ/Δ,R
1/x,R
x/x,R
Δ/Δ,R
R
1/x,L
Δ/Δ,R
B
1/1,R
0/x,L
D
0/x,R
0/0,L
1/1,L
x/x,L
Δ/Δ,R
E
Δ/Δ,R
F
x/x,R
1/x,R
Input string: 0101
q Δ0011 ⊢ ΔA0101 ⊢ ΔxC101
⊢ ΔDxx01 ⊢ DΔxx01
q
Δ/Δ,R
A
0/x,R
0/0,R
C
Δ/Δ,R
1/x,R
x/x,R
Δ/Δ,R
R
1/x,L
Δ/Δ,R
B
1/1,R
0/x,L
D
0/x,R
0/0,L
1/1,L
x/x,L
Δ/Δ,R
E
Δ/Δ,R
F
x/x,R
1/x,R
Input string: 0101
q Δ0011 ⊢ ΔA0101 ⊢ ΔxC101
⊢ ΔDxx01 ⊢ DΔxx01 ⊢ ΔExx01
q
Δ/Δ,R
A
0/x,R
0/0,R
C
Δ/Δ,R
1/x,R
x/x,R
Δ/Δ,R
R
1/x,L
Δ/Δ,R
B
1/1,R
0/x,L
D
0/x,R
0/0,L
1/1,L
x/x,L
Δ/Δ,R
E
Δ/Δ,R
F
x/x,R
1/x,R
Input string: 0101
q Δ0011 ⊢ ΔA0101 ⊢ ΔxC101
⊢ ΔDxx01 ⊢ DΔxx01 ⊢ ΔExx01
⊢ ΔxEx01
q
Δ/Δ,R
A
0/x,R
0/0,R
C
Δ/Δ,R
1/x,R
x/x,R
Δ/Δ,R
R
1/x,L
Δ/Δ,R
B
1/1,R
0/x,L
D
0/x,R
0/0,L
1/1,L
x/x,L
Δ/Δ,R
E
Δ/Δ,R
F
x/x,R
1/x,R
Input string: 0101
q Δ0011 ⊢ ΔA0101 ⊢ ΔxC101
⊢ ΔDxx01 ⊢ DΔxx01 ⊢ ΔExx01
⊢ ΔxEx01 ⊢ ΔxxE01
q
Δ/Δ,R
A
0/x,R
0/0,R
C
Δ/Δ,R
1/x,R
x/x,R
Δ/Δ,R
R
1/x,L
Δ/Δ,R
B
1/1,R
0/x,L
D
0/x,R
0/0,L
1/1,L
x/x,L
Δ/Δ,R
E
Δ/Δ,R
F
x/x,R
1/x,R
Input string: 0101
q Δ0011 ⊢ ΔA0101 ⊢ ΔxC101
⊢ ΔDxx01 ⊢ DΔxx01 ⊢ ΔExx01
⊢ ΔxEx01 ⊢ ΔxxE01 ⊢ ΔxxxC1
q
Δ/Δ,R
A
0/x,R
0/0,R
C
Δ/Δ,R
1/x,R
x/x,R
Δ/Δ,R
R
1/x,L
Δ/Δ,R
B
1/1,R
0/x,L
D
0/x,R
0/0,L
1/1,L
x/x,L
Δ/Δ,R
E
Δ/Δ,R
F
x/x,R
1/x,R
Input string: 0101
q Δ0011 ⊢ ΔA0101 ⊢ ΔxC101
⊢ ΔDxx01 ⊢ DΔxx01 ⊢ ΔExx01
⊢ ΔxEx01 ⊢ ΔxxE01 ⊢ ΔxxxC1
⊢ ΔxxDxx
q
Δ/Δ,R
A
0/x,R
0/0,R
C
Δ/Δ,R
1/x,R
x/x,R
Δ/Δ,R
R
1/x,L
Δ/Δ,R
B
1/1,R
0/x,L
D
0/x,R
0/0,L
1/1,L
x/x,L
Δ/Δ,R
E
Δ/Δ,R
F
x/x,R
1/x,R
Input string: 0101
q Δ0011 ⊢ ΔA0101 ⊢ ΔxC101
⊢ ΔDxx01 ⊢ DΔxx01 ⊢ ΔExx01
⊢ ΔxEx01 ⊢ ΔxxE01 ⊢ ΔxxxC1
⊢ ΔxxDxx ⊢ ΔxDxxx
q
Δ/Δ,R
A
0/x,R
0/0,R
C
Δ/Δ,R
1/x,R
x/x,R
Δ/Δ,R
R
1/x,L
Δ/Δ,R
B
1/1,R
0/x,L
D
0/x,R
0/0,L
1/1,L
x/x,L
Δ/Δ,R
E
Δ/Δ,R
F
x/x,R
1/x,R
Input string: 0101
q Δ0011 ⊢ ΔA0101 ⊢ ΔxC101
⊢ ΔDxx01 ⊢ DΔxx01 ⊢ ΔExx01
⊢ ΔxEx01 ⊢ ΔxxE01 ⊢ ΔxxxC1
⊢ ΔxxDxx ⊢ ΔxDxxx ⊢ ΔDxxxx
q
Δ/Δ,R
A
0/x,R
0/0,R
C
Δ/Δ,R
1/x,R
x/x,R
Δ/Δ,R
R
1/x,L
Δ/Δ,R
B
1/1,R
0/x,L
D
0/x,R
0/0,L
1/1,L
x/x,L
Δ/Δ,R
E
Δ/Δ,R
F
x/x,R
1/x,R
Input string: 0101
q Δ0011 ⊢ ΔA0101 ⊢ ΔxC101
⊢ ΔDxx01 ⊢ DΔxx01 ⊢ ΔExx01
⊢ ΔxEx01 ⊢ ΔxxE01 ⊢ ΔxxxC1
⊢ ΔxxDxx ⊢ ΔxDxxx ⊢ ΔDxxxx
⊢ DΔxxxx
q
Δ/Δ,R
A
0/x,R
0/0,R
C
Δ/Δ,R
1/x,R
x/x,R
Δ/Δ,R
R
1/x,L
Δ/Δ,R
B
1/1,R
0/x,L
D
0/x,R
0/0,L
1/1,L
x/x,L
Δ/Δ,R
E
Δ/Δ,R
F
x/x,R
1/x,R
Input string: 0101
q Δ0011 ⊢ ΔA0101 ⊢ ΔxC101
⊢ ΔDxx01 ⊢ DΔxx01 ⊢ ΔExx01
⊢ ΔxEx01 ⊢ ΔxxE01 ⊢ ΔxxxC1
⊢ ΔxxDxx ⊢ ΔxDxxx ⊢ ΔDxxxx
⊢ DΔxxxx ⊢ ΔExxxx
q
Δ/Δ,R
A
0/x,R
0/0,R
C
Δ/Δ,R
1/x,R
x/x,R
Δ/Δ,R
R
1/x,L
Δ/Δ,R
B
1/1,R
0/x,L
D
0/x,R
0/0,L
1/1,L
x/x,L
Δ/Δ,R
E
Δ/Δ,R
F
x/x,R
1/x,R
Input string: 0101
q Δ0011 ⊢ ΔA0101 ⊢ ΔxC101
⊢ ΔDxx01 ⊢ DΔxx01 ⊢ ΔExx01
⊢ ΔxEx01 ⊢ ΔxxE01 ⊢ ΔxxxC1
⊢ ΔxxDxx ⊢ ΔxDxxx ⊢ ΔDxxxx
⊢ DΔxxxx ⊢ ΔExxxx ⊢ ΔxExxx
q
Δ/Δ,R
A
0/x,R
0/0,R
C
Δ/Δ,R
1/x,R
x/x,R
Δ/Δ,R
R
1/x,L
Δ/Δ,R
B
1/1,R
0/x,L
D
0/x,R
0/0,L
1/1,L
x/x,L
Δ/Δ,R
E
Δ/Δ,R
F
x/x,R
1/x,R
Input string: 0101
q Δ0011 ⊢ ΔA0101 ⊢ ΔxC101
⊢ ΔDxx01 ⊢ DΔxx01 ⊢ ΔExx01
⊢ ΔxEx01 ⊢ ΔxxE01 ⊢ ΔxxxC1
⊢ ΔxxDxx ⊢ ΔxDxxx ⊢ ΔDxxxx
⊢ DΔxxxx ⊢ ΔExxxx ⊢ ΔxExxx
⊢ ΔxxExx
q
Δ/Δ,R
A
0/x,R
0/0,R
C
Δ/Δ,R
1/x,R
x/x,R
Δ/Δ,R
R
1/x,L
Δ/Δ,R
B
1/1,R
0/x,L
D
0/x,R
0/0,L
1/1,L
x/x,L
Δ/Δ,R
E
Δ/Δ,R
F
x/x,R
1/x,R
Input string: 0101
q Δ0011 ⊢ ΔA0101 ⊢ ΔxC101
⊢ ΔDxx01 ⊢ DΔxx01 ⊢ ΔExx01
⊢ ΔxEx01 ⊢ ΔxxE01 ⊢ ΔxxxC1
⊢ ΔxxDxx ⊢ ΔxDxxx ⊢ ΔDxxxx
⊢ DΔxxxx ⊢ ΔExxxx ⊢ ΔxExxx
⊢ ΔxxExx ⊢ ΔxxxEx
q
Δ/Δ,R
A
0/x,R
0/0,R
C
Δ/Δ,R
1/x,R
x/x,R
Δ/Δ,R
R
1/x,L
Δ/Δ,R
B
1/1,R
0/x,L
D
0/x,R
0/0,L
1/1,L
x/x,L
Δ/Δ,R
E
Δ/Δ,R
F
x/x,R
1/x,R
Input string: 0101
q Δ0011 ⊢ ΔA0101 ⊢ ΔxC101
⊢ ΔDxx01 ⊢ DΔxx01 ⊢ ΔExx01
⊢ ΔxEx01 ⊢ ΔxxE01 ⊢ ΔxxxC1
⊢ ΔxxDxx ⊢ ΔxDxxx ⊢ ΔDxxxx
⊢ DΔxxxx ⊢ ΔExxxx ⊢ ΔxExxx
⊢ ΔxxExx ⊢ ΔxxxEx ⊢ ΔxxxxEΔ
q
Δ/Δ,R
A
0/x,R
0/0,R
C
Δ/Δ,R
1/x,R
x/x,R
Δ/Δ,R
R
1/x,L
Δ/Δ,R
B
1/1,R
0/x,L
D
0/x,R
0/0,L
1/1,L
x/x,L
Δ/Δ,R
E
Δ/Δ,R
F
x/x,R
1/x,R
Input string: 0101
q Δ0011 ⊢ ΔA0101 ⊢ ΔxC101
⊢ ΔDxx01 ⊢ DΔxx01 ⊢ ΔExx01
⊢ ΔxEx01 ⊢ ΔxxE01 ⊢ ΔxxxC1
⊢ ΔxxDxx ⊢ ΔxDxxx ⊢ ΔDxxxx
⊢ DΔxxxx ⊢ ΔExxxx ⊢ ΔxExxx
⊢ ΔxxExx ⊢ ΔxxxEx ⊢ ΔxxxxEΔ
⊢ F (accept)
```