<jupyter_start><jupyter_text>The exercises below are described further [HERE](https://www.overleaf.com/read/kzjggwqbfjwd)   Tests on PDA<jupyter_code>from jove.SystemImports import *
from jove.DotBashers    import *
from jove.Def_md2mc     import *
from jove.Def_PDA       import *
from jove.Def_TM        import *
pda_a1_b2 = md2mc('''PDA
I : a, # ; cc# -> I
I : a, c ; ccc -> I
I : b, # ; b#  -> I
I : b, b ; bb  -> I
I : b, c ; ''  -> I
I : a, b ; ''  -> SeeIfMore

SeeIfMore : '', b ; ''  -> I
SeeIfMore : '', # ; c#  -> I
SeeIfMore : '', c ; cc  -> I

I : '', #; #  -> F
''')
dotObj_pda(pda_a1_b2, FuseEdges = True)
explore_pda("aabbbbbabbba", pda_a1_b2)
a1b2_s = md2mc(''' 
PDA
!!---------------------------------------------------------------------------
!! This is a PDA that accepts all strings with twice as many b's as a's
!! That is, n_b = 2 * n_a must be satisfied
!! Recall this can happen when n_a = n_b = 0 (trivial case)
!!
!! Acceptance is required to be by empty stack
!! (see a1b2_accept_f.pda for a PDA that accepts by final state)
!!
!! PDA made by markdown will have # on top of stack (TOS)
!!
!! The basic algorithm is to convert a's to  two c's
!! Only c's and b's are allowed on the stack
!! But depending on the arrival order, we need to juggle what we put on TOS
!! For details, study the comments below
!!
!!---------------------------------------------------------------------------

I : '', # ; '' ->  I    !! In case the input string is empty, we satisfy trivially

I : a, # ; cc#  -> I    !! An a coming in with # on TOS : turn a into two c

I : a, b ; ''  ->  Try  !! An a coming in with a b on TOS: we don't know what lies below b
                        !! So entry Try state, but after consuming that one b

Try : '', b ; ''  -> I  !! In Try state we find another b; how handy; consume that also
                        !! Now we are back in state I
			
Try : '', c ; cc  -> I  !! In Try state, we face a c; so we have consumed only one b
                        !! Express deficit of a 'b' by stacking a c
			
Try : '', # ; c# -> I   !! We face a #; we have again consumed only one b
                        !! Express deficit of a 'b' by stacking a c
			
I : a, c ; ccc  -> I    !! In I, we face 'c' on TOS, so express deficit of two b
       	   	   	!! by stacking two c

I : b, # ; b#   -> I	!! b input when # is TOS turns into b stacked
I : b, b ; bb   -> I    !! b input when b is TOS turns into b stacked
I : b, c ; ''   -> I    !! b and c are even match

!!---------------------------------------------------------------------------
''')
dotObj_pda(a1b2_s, FuseEdges=True) 
help(explore_pda)
explore_pda("abb", a1b2_s, acceptance='ACCEPT_S')
explore_pda("bab", a1b2_s, acceptance='ACCEPT_S')
explore_pda("bba", a1b2_s, acceptance='ACCEPT_S')
explore_pda("bbaabbbabaabbabbbb", a1b2_s, acceptance='ACCEPT_S')
explore_pda("babaababbbaabbbbbb", a1b2_s, acceptance='ACCEPT_S')
explore_pda("abbaababbbabbbbbba", a1b2_s, acceptance='ACCEPT_S')
pdaDyck = md2mc('''PDA
IF : (, #; (# -> A
A  : (, (; (( -> A
A  : ), (; '' -> A
A  : '',#; #  -> IF
''')
DOpdaDyck = dotObj_pda(pdaDyck, FuseEdges=True)
DOpdaDyck
explore_pda("", pdaDyck)
explore_pda("()", pdaDyck)
explore_pda("()()(())", pdaDyck)
explore_pda("()()(()", pdaDyck)<jupyter_output><empty_output><jupyter_text>na = nb + nc using pda<jupyter_code># Parsing an arithmetic expression
pdaE = md2mc('''PDA
!!E -> E+T | T
!!T -> T*F | F
!!F -> 2 | 3 | ~F | (E)
I : '', #  ; E#  -> M
M : '', E  ; E+T -> M
M : '', E  ; T   -> M
M : '', T  ; T*F -> M
M : '', T  ; F   -> M
M : '', F  ; 2   -> M
M : '', F  ; 3   -> M
M : '', F  ; ~F  -> M
M : '', F  ; (E) -> M
M : ~,  ~  ; ''  -> M
M : 2,  2  ; ''  -> M
M : 3,  3  ; ''  -> M
M : (,  (  ; ''  -> M
M : ),  )  ; ''  -> M
M : +,  +  ; ''  -> M
M : *,  *  ; ''  -> M
M : '', #  ; #   -> F
'''
)
DOpdaE = dotObj_pda(pdaE, FuseEdges=True)
DOpdaE
explore_pda("2+2*3", pdaE, STKMAX=7)
# Parsing an arithmetic expression
pdaEamb = md2mc('''PDA
!!E -> E * E | E + E | ~E | ( E ) | 2 | 3
I : '', #  ; E#  -> M
M : '', E  ; ~E  -> M
M : '', E  ; E+E -> M
M : '', E  ; E*E -> M
M : '', E  ; (E) -> M
M : '', E  ; 2   -> M
M : '', E  ; 3   -> M
M : ~,  ~  ; ''  -> M
M : 2,  2  ; ''  -> M
M : 3,  3  ; ''  -> M
M : (,  (  ; ''  -> M
M : ),  )  ; ''  -> M
M : +,  +  ; ''  -> M
M : *,  *  ; ''  -> M
M : '', #  ; #   -> F
'''
)
DOpdaEamb = dotObj_pda(pdaEamb, FuseEdges=True)
DOpdaEamb
explore_pda("3+2*3", pdaEamb, STKMAX=5)
3
eqpda=md2mc('''
PDA
I : a,#;a# | b,#;b# | a,a;aa | b,b;bb -> I
I : a,b;'' | b,a;'' -> I
I : '',#; # -> F
'''
           )
dotObj_pda(eqpda, FuseEdges=True)
explore_pda("aaaaaabbbbbb",eqpda)
explore_pda("",eqpda)
explore_pda("bbabaaabaabbbbaa",eqpda)
explore_pda("aaaaaabbbbb",eqpda)
chyr1pda = md2mc('''
PDA
I  : a,  # ; aa# -> I  !! bottom of the stack, push two "a"'s
I  : b,  # ; b#  -> I  !! bottom of the stack, push one "b"
I  : a,  a ; aaa -> I  !! another incoming a, put the a old "a" back and push an additional two a's
I  : b,  b ; bb  -> I  !! another incoming b, put the old "b" back and push a "b"

I  : a,  b ; ''  -> AB !! since there must be two "a"'s for every "b", remove the first "b"
AB : '', # ; a#  -> I  !! the bottom of the stack was reach with an additional "a" to add
AB : '', a ; aa  -> I  !! this really should never happen, but it's here for safety
AB : '', b ; ''  -> I  !! there was another "b", cancel this one as well

I  : b,  a ; ''  -> I  !! cancel the "b" with the "a"
I  : '', # ; #   -> F  !! the "a"'s and "b"'s cancel correctly, all done and accept!

''')
dotObj_pda(chyr1pda, FuseEdges=True)
explore_pda("babbaabbabbb",chyr1pda)
explore_pda("babbab",chyr1pda)
chyr2pda = md2mc('''
PDA
I  : a,  # ; aa# -> I  !! bottom of the stack, push two "a"'s
I  : b,  # ; b#  -> I  !! bottom of the stack, push one "b"
I  : a,  a ; aaa -> I  !! another incoming a, put the a old "a" back and push an additional two a's
I  : b,  b ; bb  -> I  !! another incoming b, put the old "b" back and push a "b"

I  : a,  b ; ''  -> AB !! since there must be two "a"'s for every "b", remove the first "b"
AB : '', # ; a#  -> I  !! the bottom of the stack was reach with an additional "a" to add
AB : '', a ; aa  -> I  !! this really should never happen, but it's here for safety
AB : '', b ; ''  -> I  !! there was another "b", cancel this one as well

I  : b,  a ; ''  -> I  !! cancel the "b" with the "a"
I  : '', # ; #   -> F  !! the "a"'s and "b"'s cancel correctly, all done and accept!

''')
explore_pda("babbab",chyr2pda)<jupyter_output><empty_output><jupyter_text>1 > 0<jupyter_code>onesGTzeros = md2mc('''PDA
I : 1,#;1# | 0,#;0  -> I
I : 1,1;11 | 0,0;00 -> I
I : 1,0;'' | 0,1;'' -> I
I : '',1;''         -> FryMyLuck
FryMyLuck : '',1;'' -> FryMyLuck
FryMyLuck : '',#;#  -> FryMyLuck
''')
dotObj_pda(onesGTzeros, FuseEdges=True)
explore_pda("11011011011", onesGTzeros)
explore_pda("1101101101100", onesGTzeros)
explore_pda("110110110110000", onesGTzeros)
explore_pda("1010110110110000", onesGTzeros)
explore_pda("10101101101100100", onesGTzeros)
explore_pda("1", onesGTzeros)
explore_pda("0", onesGTzeros)
explore_pda("", onesGTzeros)
explore_pda("1111", onesGTzeros)
explore_pda("1010101", onesGTzeros)
'''
S -> A | AS
A -> E1E
E -> 0E1E | 1E0E | ''
'''
pda1GT0 = md2mc('''
PDA

I : '' , # ; S# -> L

L : '' , S ; A  -> L

L : '' , S ; AS -> L

L : '' , A ; E1E -> L

L : '' , E ; 0E1E -> L

L : '' , E ; 1E0E -> L

L : '' , E ; ''   -> L

L : 0  , 0 ; ''   -> L

L : 1  , 1 ; ''   -> L

L : '' , # ; #    -> F

''')
dotObj_pda(pda1GT0, FuseEdges=True)
help(explore_pda)
explore_pda("1", pda1GT0, STKMAX = 8 )
explore_pda("10101", pda1GT0, STKMAX = 8 )
explore_pda("1010101", pda1GT0, STKMAX = 8 )
explore_pda("10101", pda1GT0, STKMAX = 8 )
f27sip = md2mc('''
PDA 
!!---------------------------------------
!! This is a PDA From Sipser's book
!! This matches a's and b's ignoring c's
!! or matches a's and c's, ignoring b's 
!! in the middle. Thus, the language is
!! a^m b^m c^n or a^m b^n c^m
!!---------------------------------------

!!---------------------------------------------------------------------------
!! State: in , sin ; spush -> tostates !! comment
!!---------------------------------------------------------------------------
iq2    : a  , ''  ; a     -> iq2      !!  stack a's
iq2    : '' , ''  ; ''    -> q3,q5    !!  split non-det for a^m b^m c^n (q3)
                                      !!  or a^m b^n c^m (q5)
			     
q3     : b  , a   ; ''    -> q3       !!  match b's against a's
q3     : '' , #   ; ''    -> fq4      !!  hope for acceptance when # surfaces

fq4    : c  , ''  ; ''    -> fq4      !!  be happy so long as c's come
                                      !!  will choke and reject if anything
			              !!  other than c's come

q5     : b  , ''  ; ''    -> q5       !!  here, we are going to punt over b's
q5     : '' , ''  ; ''    -> q6       !!  and non-det decide to honor c's matching
                                      !!  against a's

q6     : c  , a   ; ''    -> q6       !!  OK to match so long as c's keep coming
q6     : '' , #   ; ''    -> fq7      !!  when # surfaces, be ready to accept in
                                      !!  state fq7. However, anything else coming in
			                          !!  now will foil match and cause rejection.
!!---------------------------------------------------------------------------
''')
DOf27sip = dotObj_pda(f27sip, FuseEdges=True)
DOf27sip
explore_pda("aaabbbccc", f27sip)
wpw_tm = md2mc('''
TM
!!---------------------------------------------------------------------------
!! This is a DTM for recognizing strings of the form w#w where w is in {0,1}*
!! The presence of the "#" serves as the midpoint-marker, thus allowing the
!! TM to deterministically match around it.
!! 
!!---------------------------------------------------------------------------

!!---------------------------------------------------------------------------
!! State : rd ; wr , mv -> tostates !! comment
!!---------------------------------------------------------------------------

Iq0     : 0  ; X  , R  -> q1      !! All 0s are converted to X, and matching
	       	       	  	  !! 0s are then sought to the right of the #

Iq0     : 1  ; Y  , R  -> q7      !! All 1s are converted to Y, and matching
	       	       	  	  !! 1s are then sought to the right of the #				  
				  
Iq0     : #  ; #  , R  -> q5      !! If we see # rightaway, we are in the
	       	       	  	  !! situation of having to match eps # eps

!!---				  
q5	: X ; X,R | Y ; Y,R -> q5 !! In q5, we skip over X and Y (an equal number
	      	      	       	  !! of X and Y lie to the left of the #)

q5      : .  ; .  , R  -> Fq6	  !! .. and we accept when we see a blank (.)
!!---				  				  

q1      : 0 ; 0,R | 1 ; 1,R -> q1 !! In q1, skip over the remaining 0s and 1s

q1      : #  ; #  , R  -> q2      !! But upon seeing a #, look for a matching
	       	       	  	  !! 0 (since we are in q2, we know this).

q2      : X ; X,R | Y ; Y,R -> q2 !! All X and Y are "past stuff" to skip over

q2      : 0  ; X  , L  -> q3      !! When we find a matching 0, turn that to
	       	       	  	  !! an X, and sweep left to do the next pass
				  
q3      : X ; X,L | Y ; Y,L -> q3 !! In q3, we move over all past X, Y

q3      : #  ; #  , L  -> q4      !! but when we reach the middle marker, we
	       	       	  	  !! know that the next action is to seek the
				  !! next unprocessed 0 or 1
				  
q4      : 0 ; 0,L | 1 ; 1,L -> q4 !! In q4, wait till we hit the leftmost 0/1

q4      : X ; X,R | Y ; Y,R -> Iq0 !! When we hit an X or Y, we know that we've
 	       	       	           !! found the leftmost 0/1. Another pass begins.

!!---				  
q7      : 0 ; 0,R | 1 ; 1,R -> q7 !! q7 is similar to q1

q7      : #  ; #  , R  -> q8      !! and q8 is similar to q2

q8      : X ; X,R | Y ; Y,R -> q8 

q8      : 1  ; Y  , L  -> q3      



!!---------------------------------------------------------------------------
!! You may use the line below as an empty shell to populate for your purposes
!! Also serves as a syntax reminder for entering DFAs.
!!
!! State : r1 ; w1 , m1 | r2 ; w2 , m2 -> s1 , s2   !! comment
!!
!! ..    : .. ; .. , .. | .. ; .. , .. -> .. , ..  !!  ..
!!---------------------------------------------------------------------------
!!
!! Good commenting and software-engineering methods, good clean indentation,
!! grouping of similar states, columnar alignment, etc etc. are HUGELY
!! important in any programming endeavor -- especially while programming
!! automata. Otherwise, you can easily make a mistake in your automaton
!! code. Besides, you cannot rely upon others to find your mistakes, as
!! they will find your automaton code impossible to read!
!!
!!---------------------------------------------------------------------------

''')
    
dotObj_tm(wpw_tm, FuseEdges=True)
explore_tm(wpw_tm, "010#010", 33)
ww_ndtm = md2mc('''
TM 
!!---------------------------------------------------------------------------
!! This is a TM for ww processing. Guesses midpoint using nondet.
!! 
!!---------------------------------------------------------------------------

!!---------------------------------------------------------------------------
!! State : rd ; wr , mv -> tostates !! comment
!!---------------------------------------------------------------------------

Iq0     : 0  ; 0  , S  -> q14      !! This simulates the TM taking a guess
Iq0     : 1  ; 1  , S  -> q14      !! that it hasn't seen the midpoint. It
                                   !! moves to q14

Iq0     : .  ; .  , R  -> Fq1      !! yay! shortest acceptance is for eps eps
	                           !! i.e. facing a sea of blanks that encodes
				   !! an epsilon followed by another epsilon.

!!---------------------------------------------------------------------------
				   
q14     : 0  ; 0 , R   -> q14      !! The TM skips over 0s or
				   !! 1s for a while, and then chooses a cell,
				   
q14     : 0  ; X , L   -> q2       !! declaring it the midpoint, or more specifically
	       	       	  	   !! FIRST CHARACTER PAST MIDPOINT, by marking it 'X' 				   
				   !! and then moves to q2 (to march around the
				   !! chosen midpoint).
				   
q14     : 1  ; 1 , R   -> q14      !! Similar actions as with 0 in state q14,
q14     : 1  ; Y , L   -> q2       !! except that it "dings" the "1" with a "Y"
	       	       	  	   !! to mark it the FIRST CHARACTER PAST MIDPOINT.
				   
                                   !! Then we march around it. While the separate
				   !! use of "X" and "Y" may not be necessary,
				   !! it improves understandability when you
				   !! finally see the result of TM executions.

q2      : 0  ; 0 , L   -> q2       !! The TM is now winding back, seeking the
q2      : 1  ; 1 , L   -> q2       !! left-end of the tape till hit hits a '.'
                                   !! (blank).

q2      : .  ; . , R   -> q3       !! When that happens, the TM goes to state q3
                                   !! to begin its work of "matching around."
				   
				   !! We describe the q3,q5,q11,q9,q3 loop well.
				   !! The other loop q3,q4,q10,q8,q3 is similar.

!!-----------------------------------------------------------------

q3      : X ; X , R    -> q6       !! This state is a stuck state (no progress)
	      	       	  	   !! WE came to q3 because we dinged a 0->X
				   !! or a 1->Y while in q14; so its matching
				   !! "partner" 0 or 1 must be found to the
				   !! left. Unfortunately, we are finding an
				   !! X or a Y.  Thus, no "match around the middle"
				   !! is likely to happen.

q3      : Y ; Y , R    -> q7	   !! This state is ALSO a stuck state for similar
	      	       	  	   !! reasons as expressed in the comments
				   !! associated with q3 : X ; X ...

!!-----------------------------------------------------------------
!! Description of the q3,q5,q11,q9,q3 loop :

q3      : 1 ; Q , R    -> q5       !! Upon seeing a 1, change to Q. Then MUST see a 
                                   !! matching Y, then change to 3, and go right, and to state q5.

				   !! We do this because 'Y' represents what
				   !! was '1' and got marked as midpoint (well,
				   !! one-past midpoint..).				   

!!-- What will happen in q5,q11,q9,q3 --
				   
!! So we have to get past this assumed
!! midpoint and choose the next
!! "one past midpoint that has not been seen so far".
   
!! We enter q11 to then ding a matching
!! 0 to X or 1 to Y, moving left.
			   
!! A blank sends us leftwards, as well.
			   
!! We sweep left till we hit a Q. We MUST see a Q
!! because we entered "this lobe" by dinging a 1->Q.

!! The process repeats from state q3.



q5      : 0;0,R | 1;1,R | 2;2,R | 3;3,R -> q5  !! punt the 0/1/2/3; we need a "Y".

q5      : Y  ; 3, R               -> q11 !! ah-ha , got a Y. Ding to 3, seek 0/1/.

q11     : 1;Y,L | .;.,L | 0;X,L   -> q9  !! phew! got to sweep left now!

q9      : 0;0,L | 1;1,L | 2;2,L | 3;3,L -> q9  !! whee! going left!

q9      : Q ; Q , R                     -> q3  !! Boiinggg - now gonna go right!

!!-----------------------------------------------------------------
!! Description of the q3,q4,q10,q8,q3 loop :

q3      : 0 ; P , R    -> q4    !! This is similar to q3 : 1 ; Q , R -> q5 above


q4      : 0;0,R | 1;1,R | 2;2,R | 3;3,R -> q4  !! punt the 0/1/2/3; we need a "X".

q4      : X  ; 2, R               -> q10 !! ah-ha , got a X. Ding to 2, seek 0/1/.

q10     : 1;Y,L | .;.,L | 0;X,L   -> q8  !! phew! got to sweep left now!

q8      : 0;0,L | 1;1,L | 2;2,L | 3;3,L -> q8  !! whee! going left!

q8      : P ; P , R                     -> q3  !! Boiinggg - now gonna go right!

!!-----------------------------------------------------------------

q3      : 2;2,R | 3;3,R -> q12     !! Seeing every sign of acceptance!!

				   !! We are seeing piles of 2 and 3
				   !! ALSO did not get stuck in q6 or q7
				   !! That means all the matches went fine

q12     : 2 ; 2 , R | 3 ; 3 , R -> q12 !! Skip over piles of past 2s and 3s

q12     : . ; . , R     -> Fq13    !! Yay, acceptance when we hit a blank!


!!---------------------------------------------------------------------------
!! You may use the line below as an empty shell to populate for your purposes
!! Also serves as a syntax reminder for entering DFAs.
!!
!! State : r1 ; w1 , m1 | r2 ; w2 , m2 -> s1 , s2   !! comment
!!
!! ..    : .. ; .. , .. | .. ; .. , .. -> .. , ..  !!  ..
!!---------------------------------------------------------------------------
!!
!! Good commenting and software-engineering methods, good clean indentation,
!! grouping of similar states, columnar alignment, etc etc. are HUGELY
!! important in any programming endeavor -- especially while programming
!! automata. Otherwise, you can easily make a mistake in your automaton
!! code. Besides, you cannot rely upon others to find your mistakes, as
!! they will find your automaton code impossible to read!
!!
!!---------------------------------------------------------------------------
''')
dotObj_tm(ww_ndtm, FuseEdges=True)
explore_tm(ww_ndtm, "0101", 30)<jupyter_output><empty_output>
StarcoderdataJupyterStructuredCleanDedup