2011-05-16
Problem 2 Practice Final.
Originally Posted By: ctaslim
Problem 2
Part A
Q={q0...qn} set of states
Σ=(a1.... an} set of letters as input
Γ={a1...an,[]}
δ={
- qk ia any stake
- ak is any tape alphabet symbol
(qk,ak)->(ak,ak,up)
(qk,ak)->(ak,ak,down)
(qk,ak)->(ak,ak,left)
(qk,ak)->(ak,ak,right)
(qk,[])->(ak,ak,stay put)}
qo=start state
Part B
1. The rows of the 2D tape starting from the “bottom-most” row are written in the 1D tape next to each other, as in the figure below. Note that this is indeed possible, because at any point of time, the TM has looked at only a finite number of rows, and a finite number of tape squares in each row.
2. When the machine tries to move right from a square in the 2D tape, we can simulate it in the 1D tape trivially, except when it tries to move right from the rightmost square in a row. In that case, we “make room” for the new tape square by moving all the symbols to the right. For instance, when the machine tries to move right after reading in the figure, we simulate the effect in the 1D tape as follows: We move all the symbols starting from the right after in the 1D tape, one square to the right. In the newly vacant square, we write a blank, and continue simulating.
3. When the machine tries to move left from the leftmost square in a row, we do nothing (The machine hits the wall). Otherwise, we can trivially simulate it in the 1D tape.
4.When the machine tries to move up, we move left until we reach a symbol to determine which column we are in. Then we move right beyond the nextand into the corresponding column one row up. (To count, we might use an auxiliary tape and later use the 2-tape TM to 1-tape TM conversion). If there is not enough room in the next row, we make room by moving all the tape squares to the right, just as in step .The machine tries to move down. We proceed exactly as in Step except that now, we move one row down. In case we are in the bottommost row, we do nothing. (Again, the machine hits the wall).
The names of the group : Christopher Taslim, Hamzeh Doostie, and ....(I don't know the third member's name), i'll found out after this post
Part A
Q={q0...qn} set of states
Σ=(a1.... an} set of letters as input
Γ={a1...an,[]}
δ={
- qk ia any stake
- ak is any tape alphabet symbol
(qk,ak)->(ak,ak,up)
(qk,ak)->(ak,ak,down)
(qk,ak)->(ak,ak,left)
(qk,ak)->(ak,ak,right)
(qk,[])->(ak,ak,stay put)}
qo=start state
Part B
1. The rows of the 2D tape starting from the “bottom-most” row are written in the 1D tape next to each other, as in the figure below. Note that this is indeed possible, because at any point of time, the TM has looked at only a finite number of rows, and a finite number of tape squares in each row.
2. When the machine tries to move right from a square in the 2D tape, we can simulate it in the 1D tape trivially, except when it tries to move right from the rightmost square in a row. In that case, we “make room” for the new tape square by moving all the symbols to the right. For instance, when the machine tries to move right after reading in the figure, we simulate the effect in the 1D tape as follows: We move all the symbols starting from the right after in the 1D tape, one square to the right. In the newly vacant square, we write a blank, and continue simulating.
3. When the machine tries to move left from the leftmost square in a row, we do nothing (The machine hits the wall). Otherwise, we can trivially simulate it in the 1D tape.
4.When the machine tries to move up, we move left until we reach a symbol to determine which column we are in. Then we move right beyond the nextand into the corresponding column one row up. (To count, we might use an auxiliary tape and later use the 2-tape TM to 1-tape TM conversion). If there is not enough room in the next row, we make room by moving all the tape squares to the right, just as in step .The machine tries to move down. We proceed exactly as in Step except that now, we move one row down. In case we are in the bottommost row, we do nothing. (Again, the machine hits the wall).
The names of the group : Christopher Taslim, Hamzeh Doostie, and ....(I don't know the third member's name), i'll found out after this post
'''Originally Posted By: ctaslim'''
Problem 2<br><br>Part A<br>Q={q0...qn} set of states<br>Σ=(a1.... an} set of letters as input<br>Γ={a1...an,[]}<br>δ={<br>- qk ia any stake<br>- ak is any tape alphabet symbol<br>(qk,ak)->(ak,ak,up)<br>(qk,ak)->(ak,ak,down)<br>(qk,ak)->(ak,ak,left)<br>(qk,ak)->(ak,ak,right)<br>(qk,[])->(ak,ak,stay put)}<br>qo=start state<br><br>Part B<br>1. The rows of the 2D tape starting from the “bottom-most” row are written in the 1D tape next to each other, as in the figure below. Note that this is indeed possible, because at any point of time, the TM has looked at only a finite number of rows, and a finite number of tape squares in each row.<br>2. When the machine tries to move right from a square in the 2D tape, we can simulate it in the 1D tape trivially, except when it tries to move right from the rightmost square in a row. In that case, we “make room” for the new tape square by moving all the symbols to the right. For instance, when the machine tries to move right after reading in the figure, we simulate the effect in the 1D tape as follows: We move all the symbols starting from the right after in the 1D tape, one square to the right. In the newly vacant square, we write a blank, and continue simulating.<br>3. When the machine tries to move left from the leftmost square in a row, we do nothing (The machine hits the wall). Otherwise, we can trivially simulate it in the 1D tape.<br>4.When the machine tries to move up, we move left until we reach a symbol to determine which column we are in. Then we move right beyond the nextand into the corresponding column one row up. (To count, we might use an auxiliary tape and later use the 2-tape TM to 1-tape TM conversion). If there is not enough room in the next row, we make room by moving all the tape squares to the right, just as in step .The machine tries to move down. We proceed exactly as in Step except that now, we move one row down. In case we are in the bottommost row, we do nothing. (Again, the machine hits the wall).<br><br>The names of the group : Christopher Taslim, Hamzeh Doostie, and ....(I don't know the third member's name), i'll found out after this post
Originally Posted By: ctaslim
third member: Andrey Andreev
'''Originally Posted By: ctaslim'''
third member: Andrey Andreev
2011-05-18
Your transition function seems a bit messed up. Rather than:
(qk,ak)->(ak,ak, direction)
maybe something like:
(q_k,a_k)->(q_j,a_k, direction)
i.e., you have to say something about what state you go to next.
Your proof could probably be made to work.
(qk,ak)->(ak,ak, direction)
maybe something like:
(q_k,a_k)->(q_j,a_k, direction)
i.e., you have to say something about what state you go to next.
Your proof could probably be made to work.
Your transition function seems a bit messed up. Rather than:<br>(qk,ak)->(ak,ak, direction)<br><br>maybe something like:<br>(q_k,a_k)->(q_j,a_k, direction)<br>i.e., you have to say something about what state you go to next.<br><br>Your proof could probably be made to work.
(c) 2024 Yioop - PHP Search Engine