According to the description below: ///////////////////////////////////////////////////////////////////////////////////// w contains an equal number of 0's and 1's and w contains exactly 1 '#' $ $ 0 1 0 1 # $ $ Pseudocode to check if there is same number of 0s and 1s and only one #: 1. Move right , Read first leftmost 0, replace with X (0->X) 2. Keep moving to the left until you encounter $. 3. Move right, read first leftmost 1, replace 1 with X(1->X) 4.Keep moving to the left until you encounter $. 5. Move right, read first leftmost #, replace # with X(#->X) 6. Keep moving to the left until you encounter $. 7. repeat steps 1 to 4 until you encounter $ as input 8. Halt if there is only string of X's --------------------------------------------------------- 1.Check 10#∈B It contains equal number of 0's and 1's and exactly one '#'. It is accepted 2.Check 01#10 ∈ B It is accepted It contains equal number of 0's and 1's and exactly one '#'. 3.Check 01##01 ∄ band It is not accepted It does not contains equal number of 0's and 1's and exactly one '#'. 4.Check #001 ∄ B. It does not contains equal number of 0's and 1's and exactly one '#'. It is not accepted. ///////////////////////////////////////////////////////////////////////////////////// then construct a state-diagram representation of Turing Machine. In this case, you are required to use 2 tape TM and the stay option. Please remember to state the expected final configuration of the main tape given your design of Turing Machine for this problem.
According to the description below:
/////////////////////////////////////////////////////////////////////////////////////
w contains an equal number of 0's and 1's and w contains exactly 1 '#'
$ $ 0 1 0 1 # $ $
Pseudocode to check if there is same number of 0s and 1s and only one #:
1. Move right , Read first leftmost 0, replace with X (0->X)
2. Keep moving to the left until you encounter $.
3. Move right, read first leftmost 1, replace 1 with X(1->X)
4.Keep moving to the left until you encounter $.
5. Move right, read first leftmost #, replace # with X(#->X)
6. Keep moving to the left until you encounter $.
7. repeat steps 1 to 4 until you encounter $ as input
8. Halt if there is only string of X's
---------------------------------------------------------
1.Check 10#∈B
It contains equal number of 0's and 1's and exactly one '#'.
It is accepted
2.Check 01#10 ∈ B
It is accepted
It contains equal number of 0's and 1's and exactly one '#'.
3.Check 01##01 ∄ band
It is not accepted
It does not contains equal number of 0's and 1's and exactly one '#'.
4.Check #001 ∄ B.
It does not contains equal number of 0's and 1's and exactly one '#'.
It is not accepted.
/////////////////////////////////////////////////////////////////////////////////////
then construct a state-diagram representation of Turing Machine. In this case, you are required to use 2 tape TM and the stay option. Please remember to state the expected final configuration of the main tape given your design of Turing Machine for this problem.
Trending now
This is a popular solution!
Step by step
Solved in 4 steps with 1 images
