Skip to content
Permalink
master
Switch branches/tags

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

Go to file
 
 
Cannot retrieve contributors at this time
245 lines (189 sloc) 6.38 KB
Raw Blame
Open in GitHub Desktop
;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