Permalink
Cannot retrieve contributors at this time
;Renoj Varghese | |
;1a. | |
;Name: Example 3.7 | |
;checks if number of 0s are a power of 2 | |
;Inputs Checked | |
;"" : halt-reject | |
;"0" : halt-accept | |
;"00": halt-accept | |
;"000": halt-reject | |
;"000000000": halt-reject | |
;"0000000000000000": halt-accept | |
;Machine starts in state q1. | |
;q1: check for no 0s | |
q1 0 _ R q2 | |
q1 x x R halt-reject | |
q1 _ _ R halt-reject | |
;q2 replace 0s with x's | |
q2 0 x R q3 | |
q2 x x R q2 | |
q2 _ _ R halt-accept ;represents accept state | |
;q3 move Right of x's | |
q3 0 0 R q4 | |
q3 x x R q3 | |
q3 _ _ L q5 | |
;q4 replace 0s with x's | |
q4 0 x R q3 | |
q4 x x R q4 | |
q4 _ _ R halt-reject ;represents reject state | |
;q5 move L until beginning of string | |
q5 0 0 L q5 | |
q5 x x L q5 | |
q5 _ _ R q2 | |
Renoj Varghese | |
;1b. | |
;Title: M$ | |
;Program to move input string over 1 position and add a $ before input | |
;Input Tests | |
;"" : halt-accept, tape: $_, head over _ | |
;"a" : halt-accept, tape: $a, head over a | |
;"cab" :halt-accept, tape: $cab, head over c | |
;"bbbbbb": halt-accept, tape: $bbbbbb, head over first b | |
;"abccba" : halt-accept, tape: $abccba, head over first a | |
;"abababababababababac": halt-accept, tape: $abababababababababac, head over first a | |
;Initial State q1 | |
;$q1 represents an initial state that will begin insert a $ and the first char | |
$q1 a $ R $needA | |
$q1 b $ R $needB | |
$q1 c $ R $needC | |
$q1 _ $ R $moveBack | |
$q1 $ $ R halt-reject ;should never run into $ again (not part of sigma) | |
;$needA tells machine that the next char should be an a | |
$needA a a R $needA | |
$needA b a R $needB | |
$needA c a R $needC | |
$needA _ a R $moveBack | |
$needA $ $ R halt-reject ;should never run into $ again (not part of sigma) | |
;$needB tells machine that the next char should be an b | |
$needB a b R $needA | |
$needB b b R $needB | |
$needB c b R $needC | |
$needB _ b R $moveBack | |
$needB $ $ R halt-reject ;should never run into $ again (not part of sigma) | |
;$needC tells machine that the next char should be an a | |
$needC a c R $needA | |
$needC b c R $needB | |
$needC c c R $needC | |
$needC _ c R $moveBack | |
$needC $ $ R halt-reject ;should never run into $ again (not part of sigma) | |
;$moveBack tells machine that a blank has been reached and move back to $ | |
$moveBack a a L $moveBack | |
$moveBack b b L $moveBack | |
$moveBack c c L $moveBack | |
$moveBack _ _ L $moveBack | |
$moveBack $ $ R halt-accept | |
;Renoj Varghese | |
;1c. | |
;Title: M# | |
;Program to move input string over 1 position and add a # before input | |
;initial state is #q1 | |
;Input Tests | |
;"" : halt-accept, tape: #_, head over _ | |
;"a" : halt-accept, tape: #a, head over a | |
;"cab" :halt-accept, tape: #cab, head over c | |
;"bbbbbb": halt-accept, tape: #bbbbbb, head over first b | |
;"abccba" : halt-accept, tape: #abccba, head over first a | |
;"abababababababababac": halt-accept, tape: #abababababababababac, head over first a | |
;#q1 represents an initial state that will begin insert a # and the first char | |
#q1 a # R #needA | |
#q1 b # R #needB | |
#q1 c # R #needC | |
#q1 _ # R #moveBack | |
#q1 # # R halt-reject ;should never run into # again (not part of sigma) | |
;#needA tells machine that the next char should be an a | |
#needA a a R #needA | |
#needA b a R #needB | |
#needA c a R #needC | |
#needA _ a R #moveBack | |
#needA # # R halt-reject ;should never run into # again (not part of sigma) | |
;#needB tells machine that the next char should be an b | |
#needB a b R #needA | |
#needB b b R #needB | |
#needB c b R #needC | |
#needB _ b R #moveBack | |
#needB # # R halt-reject ;should never run into # again (not part of sigma) | |
;#needC tells machine that the next char should be an a | |
#needC a c R #needA | |
#needC b c R #needB | |
#needC c c R #needC | |
#needC _ c R #moveBack | |
#needC # # R halt-reject ;should never run into # again (not part of sigma) | |
;#moveBack tells machine that a blank has been reached and move back to # | |
#moveBack a a L #moveBack | |
#moveBack b b L #moveBack | |
#moveBack c c L #moveBack | |
#moveBack _ _ L #moveBack | |
#moveBack # # R halt-accept ;accept state for M# | |
;Renoj Varghese | |
;1d. | |
;Title: M$# | |
;Program to move input string over 1 position and add a $# before input | |
;********Only change is that all transitions to accept state for M$, halt-accept changed to transition to #q1 | |
;initial state is $q1 | |
;Input Tests | |
;"" : halt-accept, tape: $#_, head over _ | |
;"a" : halt-accept, tape: $#a, head over a | |
;"cab" :halt-accept, tape: $#cab, head over c | |
;"bbbbbb": halt-accept, tape: $#bbbbbb, head over first b | |
;"abccba" : halt-accept, tape: $#abccba, head over first a | |
;"abababababababababac": halt-accept, tape: $#abababababababababac, head over first a | |
;$q1 represents an initial state that will begin insert a $ and the first char | |
$q1 a $ R $needA | |
$q1 b $ R $needB | |
$q1 c $ R $needC | |
$q1 _ $ R $moveBack | |
$q1 $ $ R halt-reject ;should never run into $ again (not part of sigma) | |
;$needA tells machine that the next char should be an a | |
$needA a a R $needA | |
$needA b a R $needB | |
$needA c a R $needC | |
$needA _ a R $moveBack | |
$needA $ $ R halt-reject ;should never run into $ again (not part of sigma) | |
;$needB tells machine that the next char should be an b | |
$needB a b R $needA | |
$needB b b R $needB | |
$needB c b R $needC | |
$needB _ b R $moveBack | |
$needB $ $ R halt-reject ;should never run into $ again (not part of sigma) | |
;$needC tells machine that the next char should be an a | |
$needC a c R $needA | |
$needC b c R $needB | |
$needC c c R $needC | |
$needC _ c R $moveBack | |
$needC $ $ R halt-reject ;should never run into $ again (not part of sigma) | |
;$moveBack tells machine that a blank has been reached and move back to $ | |
$moveBack a a L $moveBack | |
$moveBack b b L $moveBack | |
$moveBack c c L $moveBack | |
$moveBack _ _ L $moveBack | |
$moveBack $ $ R #q1 | |
;#q1 represents an initial state that will begin insert a # and the first char | |
#q1 a # R #needA | |
#q1 b # R #needB | |
#q1 c # R #needC | |
#q1 _ # R #moveBack | |
#q1 # # R halt-reject ;should never run into # again (not part of sigma) | |
;#needA tells machine that the next char should be an a | |
#needA a a R #needA | |
#needA b a R #needB | |
#needA c a R #needC | |
#needA _ a R #moveBack | |
#needA # # R halt-reject ;should never run into # again (not part of sigma) | |
;#needB tells machine that the next char should be an b | |
#needB a b R #needA | |
#needB b b R #needB | |
#needB c b R #needC | |
#needB _ b R #moveBack | |
#needB # # R halt-reject ;should never run into # again (not part of sigma) | |
;#needC tells machine that the next char should be an a | |
#needC a c R #needA | |
#needC b c R #needB | |
#needC c c R #needC | |
#needC _ c R #moveBack | |
#needC # # R halt-reject ;should never run into # again (not part of sigma) | |
;#moveBack tells machine that a blank has been reached and move back to # | |
#moveBack a a L #moveBack | |
#moveBack b b L #moveBack | |
#moveBack c c L #moveBack | |
#moveBack _ _ L #moveBack | |
#moveBack # # R halt-accept | |