Permalink
Cannot retrieve contributors at this time
Name already in use
A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?
Student-Admin-Redesign/src/resources/CSE3502HW6_TM.txt
Go to fileThis commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
245 lines (189 sloc)
6.38 KB
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
;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 | |