<jupyter_start><jupyter_text>**Here is how we will represent a DFA in Python (taking Figure 3.4's example from the book). You can clearly see how the traits of the DFA are encoded. We prefer a Python dictionary, as it supports a number of convenient operations, and also one can add additional fields easily. **<jupyter_code>DFA_fig34 = { 'Q': {'A', 'IF', 'B'},
              'Sigma': {'0', '1'},
              'Delta': { ('IF', '0'): 'A',
                         ('IF', '1'): 'IF',
                         ('A', '0'): 'B',
                         ('A', '1'): 'A',
                         ('B', '0'): 'IF',
                         ('B', '1'): 'B' },
              'q0': 'IF', 
              'F': {'IF'}   
            }<jupyter_output><empty_output><jupyter_text>**We can now write routines to print DFA using dot. The main routines are listed below.** * dot_dfa_w_bh : lists all states of a DFA including black-hole states* dot_dfa      : lists all isNotBH states (see below for a defn), i.e. suppress black-holes     - Usually there are too many transitions to them and that clutters the view      ======<jupyter_code># Some tests pertaining to totalize_dfa, is_consistent_dfa, etc

DFA_fig34 = { 'Q': {'A', 'IF', 'B'},
              'Sigma': {'0', '1'},
              'Delta': { ('IF', '0'): 'A',
                         ('IF', '1'): 'IF',
                         ('A', '0'): 'B',
                         ('A', '1'): 'A',
                         ('B', '0'): 'IF',
                         ('B', '1'): 'B' },
              'q0': 'IF', 
              'F': {'IF'}   
            }

def tests_dfa_consist():
    """Some tests wrt DFA routines.
    """
    DFA_fig34_Q     = DFA_fig34["Q"]
    DFA_fig34_Sigma = DFA_fig34["Sigma"]
    randQ           = random.choice(list(DFA_fig34_Q))
    randSym         = random.choice(list(DFA_fig34_Sigma))

    DFA_fig34_deepcopy  = copy.deepcopy(DFA_fig34)

    print('is_consistent_dfa(DFA_fig34) =', 
           is_consistent_dfa(DFA_fig34) )
    print('Removing mapping for ' + 
          "(" + randQ + "," + randSym + ")" + 
          "from DFA_fig34_deepcopy")
    DFA_fig34_deepcopy["Delta"].pop((randQ,randSym))
    print('is_consistent_dfa(DFA_fig34_deepcopy) =', 
         is_consistent_dfa(DFA_fig34_deepcopy) )

    totalized = totalize_dfa(DFA_fig34_deepcopy)
    print ( 'is_consistent_dfa(totalized) =', 
          is_consistent_dfa(totalized) )

    assert(totalized == totalize_dfa(totalized)) # Must pass  
dfaBESame = md2mc('''
DFA !! Begins and ends with same; epsilon allowed
IF  : 0 -> F0
IF  : 1 -> F1
!!
F0  : 0 -> F0
F0  : 1 -> S01
S01 : 1 -> S01
S01 : 0 -> F0
!!
F1  : 1 -> F1
F1  : 0 -> S10
S10 : 0 -> S10
S10 : 1 -> F1
''')
DOdfaBESame = dotObj_dfa(dfaBESame)
DOdfaBESame
DOdfaBESame.source<jupyter_output><empty_output><jupyter_text>Let us now administer some tests to print dot-strings generated.We will demonstrate two ways to print automata: 1. First generate a dot string via dot_dfa or dot_dfa_w_bh   (calling the result "dot_string")    1. Then use the srcObj = Source(dot_string) call   2. Thereafter we can display the srcObj object directly into the browser   3. Or, one can also later convert the dot_string to svg or PDF2. OR, one can directly generate a dot object via the dotObj_dfa or dotObj_dfa_w_bh call   (calling the result "dot_object")   1. Then directly display the dot_object   2. There are conversions available for dot_object to other formats too<jupyter_code>DFA_fig34 = { 'Q': {'A', 'IF', 'B'},
              'Sigma': {'0', '1'},
              'Delta': { ('IF', '0'): 'A',
                         ('IF', '1'): 'IF',
                         ('A', '0'): 'B',
                         ('A', '1'): 'A',
                         ('B', '0'): 'IF',
                         ('B', '1'): 'B' },
              'q0': 'IF', 
              'F': {'IF'}   
            }

def dfa_dot_tests():
    """Some dot-routine related tests.
    """
    dot_string = dot_dfa(DFA_fig34)
    dot_object1 = Source(dot_string)
    return dot_object1.source<jupyter_output><empty_output><jupyter_text>Let us test functions step_dfa, run_dfa, and accepts_dfa<jupyter_code># Some tests of step, run, etc.

DFA_fig34 = { 'Q': {'A', 'IF', 'B'},
              'Sigma': {'0', '1'},
              'Delta': { ('IF', '0'): 'A',
                         ('IF', '1'): 'IF',
                         ('A', '0'): 'B',
                         ('A', '1'): 'A',
                         ('B', '0'): 'IF',
                         ('B', '1'): 'B' },
              'q0': 'IF', 
              'F': {'IF'}   
            }

def step_run_accepts_tests():
    print("step_dfa(DFA_fig34, 'IF', '1') = ", 
          step_dfa(DFA_fig34, 'IF', '1'))
    print("step_dfa(DFA_fig34, 'A', '0') = ", 
          step_dfa(DFA_fig34, 'A', '0'))

    print("run_dfa(DFA_fig34, '101001') = ", 
          run_dfa(DFA_fig34, '101001'))
    print("run_dfa(DFA_fig34, '101000') = ", 
          run_dfa(DFA_fig34, '101000'))

    print("accepts_dfa(DFA_fig34, '101001') = ", 
          accepts_dfa(DFA_fig34, '101001')) 
    print("accepts_dfa(DFA_fig34, '101000') = ", 
          accepts_dfa(DFA_fig34, '101000')) 
dotObj_dfa(DFA_fig34, "DFA_fig34")
# Run a complementation test
DFA_fig34_comp = comp_dfa(DFA_fig34)
dotObj_dfa(DFA_fig34_comp, "DFA_fig34_comp")
dotObj_dfa(DFA_fig34)
dotObj_dfa(DFA_fig34_comp, "DFA_fig34_comp")
dotObj_dfa(DFA_fig34_comp)
# One more test
du     = union_dfa(DFA_fig34, DFA_fig34_comp)
dotObj_dfa(du, "orig union")
pdu    = pruneUnreach(du)
pdu
pduObj = dotObj_dfa(pdu, "union of 34 and comp")
pduObj


D34 = {   'Q': {'A', 'IF', 'B'},
          'Sigma': {'0', '1'},
          'Delta': { ('IF', '0'): 'A',
                     ('IF', '1'): 'IF',
                     ('A', '0'): 'B',
                     ('A', '1'): 'A',
                     ('B', '0'): 'IF',
                     ('B', '1'): 'B' },
          'q0': 'IF', 
          'F': {'IF'}   
        }

D34bl = { 'Q': {'A', 'IF', 'B', 'A1', 'B1'},
          'Sigma': {'0', '1'},
          'Delta': { ('IF', '0'): 'A',
                     ('IF', '1'): 'IF',
                     ('A', '0'): 'B1',
                     ('A', '1'): 'A1',
                     ('A1', '0'): 'B',
                     ('A1', '1'): 'A',
                     ('B1', '0'): 'IF',
                     ('B1', '1'): 'B',
                     ('B','0') : 'IF',
                     ('B', '1'): 'B1' },
          'q0': 'IF', 
          'F': {'IF'}   
        }


d34 = dotObj_dfa(D34, "D34")
d34 # Display it!
langeq_dfa(D34,D34bl,False)
iso_dfa(D34,D34bl)
DFA_fig34
d34 = DFA_fig34
d34
d34c = DFA_fig34_comp
d34c
iso_dfa(d34,d34)
iso_dfa(d34,d34c)
d34v1 = {'Delta': {('A', '0'): 'B',
  ('A', '1'): 'B',
  ('B', '0'): 'IF',
  ('B', '1'): 'B',
  ('IF', '0'): 'A',
  ('IF', '1'): 'IF'},
 'F': {'IF'},
 'Q': {'A', 'B', 'IF'},
 'Sigma': {'0', '1'},
 'q0': 'IF'}
dotObj_dfa(d34v1)
d34v2 = {'Delta': {('A', '0'): 'B',
  ('A', '1'): 'B',
  ('B', '0'): 'IF',
  ('B', '1'): 'B',
  ('IF', '0'): 'A',
  ('IF', '1'): 'IF'},
 'F': {'IF', 'B'},
 'Q': {'A', 'B', 'IF'},
 'Sigma': {'0', '1'},
 'q0': 'IF'}
iso_dfa(d34,d34v1)
iso_dfa(d34,d34v2)
iso_dfa(d34v1,d34v2)
div1 = pruneUnreach(intersect_dfa(d34v1,d34v2))
dotObj_dfa(div1)
div2 = pruneUnreach(union_dfa(d34v1,d34v2))
dotObj_dfa(div2)
iso_dfa(div1,div2)
langeq_dfa(div1,div2,True)
d34bl = dotObj_dfa(D34bl, "D34bl")
d34bl # Display it!
d34bl = dotObj_dfa(D34bl, FuseEdges=True, dfaName="D34bl")
d34bl
iso_dfa(D34,D34bl)
langeq_dfa(D34,D34bl)<jupyter_output><empty_output><jupyter_text><jupyter_code>du
dotObj_dfa(pruneUnreach(D34bl), "D34bl")
### DFA minimization (another example)
Bloat1 = {'Q': {'S1', 'S3', 'S2', 'S5', 'S4', 'S6' },
          'Sigma': {'b', 'a'},
          'Delta': { ('S1','b') : 'S3',
                     ('S1','a') : 'S2',
                     ('S3','a') : 'S5',
                     ('S2','a') : 'S4',
                     ('S3','b') : 'S4',
                     ('S2','b') : 'S5',
                     ('S5','b') : 'S6',
                     ('S5','a') : 'S6',
                     ('S4','b') : 'S6',
                     ('S4','a') : 'S6',
                     ('S6','b') : 'S6',
                     ('S6','a') : 'S6' },
          'q0': 'S1', 
          'F': {'S2','S3','S6'}   
        }


Bloat1O = dotObj_dfa(Bloat1, dfaName="Bloat1")
Bloat1O # Display it!
dotObj_dfa(Bloat1, FuseEdges=True, dfaName="Bloat1")
bloated_dfa = md2mc('''
DFA
IS1 : a -> FS2
IS1 : b -> FS3
FS2 : a -> S4
FS2 : b -> S5
FS3 : a -> S5
FS3 : b -> S4
S4  : a | b -> FS6
S5  : a | b -> FS6
FS6 : a | b -> FS6
''')
dotObj_dfa(bloated_dfa)
dotObj_dfa(bloated_dfa).source<jupyter_output><empty_output><jupyter_text>Now, here is how the computation proceeds for this example:--------------------------------------------------------     ``` Frame-0                  Frame-1                   Frame-2                                                                                                                         S2  -1                   S2   0                    S2   0                     S3  -1  -1               S3   0  -1                S3   0  -1                 S4  -1  -1  -1           S4  -1   0   0            S4   2   0   0             S5  -1  -1  -1  -1       S5  -1   0   0  -1        S5   2   0   0  -1         S6  -1  -1  -1  -1  -1   S6   0  -1  -1   0   0    S6   0   1   1   0   0         S1  S2  S3  S4  S5       S1  S2  S3  S4  S5        S1  S2  S3  S4  S5        Initial                  0-distinguishable         1-distinguishable                                   Frame-3                 Frame-4                             =                        Frame-3S2   0S3   0  -1S4   2   0   0S5   2   0   0  -1S6   0   1   1   0   0    S1  S2  S3  S4  S5    2-distinguishable      ``` Here is the algorithm, going frame by frame.- Initial Frame:      The initial frame is drawn to clash all _combinations_ of states taken two at a time.     Since we have 6 states, we have $6\choose 2$ = $15$ entries. We put a -1 against each     such pair to denote that they have not been found distinguishable yet.- Frame *0-distinguishable*: We now put a 0 where a pair of states is 0-distinguishable. This means the states are distinguisable after consuming $\varepsilon$. This of course means that the states are themselves distinguishable. This is only possible if one is a final state and the other is not (in that case, one state, after consuming $\varepsilon$ accepts_dfa, and another state after consuming $\varepsilon$ does not accept.  - So for instance, notice that (S3,S1) and (S4,S2) are 0-distinguishable, meaning that one is a final and the other is a non-final state.- Frame *1-distinguishable*: We now put a 1 where a pair of states is 1-distinguishable. This means the states are distinguisable after consuming a string of length $1$ (a single symbol). This is only possible if one state transitions to a final state and the other transitions to a non-final state after consuming a member of $\Sigma$.   State pairs (S6,S2) and (S6,S3) are of this kind. While both S6 and S2 are final states (hence _0-indistinguishable_), after consuming an 'a' (or a 'b') they respectively go to a final/non-final state. This means that  - after processing **the same symbol** one state -- let's say pre_p -- finds itself landing in a state p and another state  -- let's say pre_q -- finds itself landing in a state q such that (p,q) is 0-distinguishable.    - When this happens, states pre-p and pre-q are **1-distinguishable**.- Frame *2-distinguishable*: We now put a 2 where a pair of states is 2-distinguishable. This means the states are distinguisable after consuming a string of length $2$ (a string of length $2$). This is only possible if one state transitions to a state (say p) and the other transitions to state (say q) after consuming a member of $\Sigma$ such that (p,q) is **1-distinguishable**. State pairs (S5,S1) and (S4,S1) are 2-distinguishable because  - after processing **the same symbol** one state -- let's say pre_p -- finds itself landing in a state p and another state  -- let's say pre_q -- finds itself landing in a state q such that (p,q) is 0-distinguishable.    - When this happens, states pre-p and pre-q are **1-distinguishable**.    - One example is this:      - S5 and S1 are 2-distinguishable.        - This is because after seeing an 'aa', S1 lands in a non-final state while S5 lands in a final state        - Observe that "aa" = "a" + "a" . Thus, after eating the first "a", S1 lands in S2 while S5 lands in S6, and (S2,S6) have already been deemed 1-distinguishable.        - Thus, when we mark (S5,S1) as 2-distinguishable, we are sending the matrix entry at (S5,S2) from       -1 to 2   - Now, in search of 3-distinguishability, we catch hold of all pairs in the matrix and see if we can send another -1 entry to "3". This appears not to happen.        - Thus, if (S2,S3) is pushed via any sequence of symbols (any string) of any length, it       always stays in the same type of state. Thus, after seeing 'ababba', S2 is in S6, while S3         is also in S6. - Thus, given no changes in the matrix, we stop.<jupyter_code>dotObj_dfa(min_dfa(Bloat1), FuseEdges=True, dfaName="shrunkBloat1")
min_bloat = min_dfa(Bloat1)
dotObj_dfa(min_bloat).source
prd34b1 = pruneUnreach(D34bl)
dotObj_dfa(prd34b1, "prd34b1")
dotObj_dfa(min_dfa(prd34b1), "prd34b1min")
third1dfa=md2mc(src="File", fname="machines/dfafiles/thirdlastis1.dfa")
third1dfa
dotObj_dfa(third1dfa)
ends0101 =\
"\
DFA\
 \
I     : 0 -> S0 \
I     : 1 -> I \
S0    : 0 -> S0 \
S0    : 1 -> S01 \
S01   : 0 -> S010 \
S01   : 1 -> I \
S010  : 0 -> S0 \
S010  : 1 -> F0101 \
F0101 : 0 -> S010 \
F0101 : 1 -> I \
"
ends0101
dfaends0101=md2mc(ends0101)
dfaends0101
dped1 = md2mc(src="File", fname="machines/dfafiles/pedagogical1.dfa")
#machines/dfafiles/pedagogical1.dfa
dped1
dotObj_dfa(dped1)
dotObj_dfa(dped1, FuseEdges=True)
dotObj_dfa(md2mc(ends0101))
thirdlastis1=md2mc(src="File", fname="machines/dfafiles/thirdlastis1.dfa")
#machines/dfafiles/thirdlastis1.dfa
thirdlastis1
dotObj_dfa(thirdlastis1)
dped1=md2mc(src="File", fname="machines/dfafiles/pedagogical2.dfa")
#machines/dfafiles/pedagogical2.dfa
dotObj_dfa(dped1)
secondLastIs1 = md2mc('''
!!------------------------------------------------------------
!! This DFA looks for patterns of the form ....1.
!! i.e., the second-last (counting from the end-point) is a 1
!!
!! DFAs find such patterns "very stressful to handle",
!! as they are kept guessing of the form  'are we there yet?'
!! 'are we seeing the second-last' ?
!! They must keep all the failure options at hand. Even after
!! a 'fleeting glimpse' of the second-last, more inputs can
!! come barreling-in to make that "lucky 1" a non-second-last.
!!
!! We take 7 states in the DFA solution.
!!------------------------------------------------------------

DFA
!!------------------------------------------------------------
!! State : in ->  tostate !! comment
!!------------------------------------------------------------

I   :  0 ->  S0  !! Enter at init state I
I   :  1 ->  S1  !! Record bit seen in state letter
                     !! i.e., S0 means "state after seeing a 0"
			 
S0  :  0 ->  S00 !! continue recording input seen
S0  :  1 ->  S01 !! in state-letter. This is a problem-specific
                 !! way of compressing the input seen so far.

S1  :  0 ->  F10 !! We now have a "second last" available!
S1  :  1 ->  F11 !! Both F10 and F10 are "F" (final)

S00 :  0 ->  S00 !! History of things seen is still 00
S00 :  1 ->  S01 !! Remember 01 in the state

S01 :  0 ->  F10 !! We again have a second-last of 1
S01 :  1 ->  F11 !! We are in F11 because of 11 being last seen

F10 :  0 ->  S00 !! The second-last 1 gets pushed-out
F10 :  1 ->  S01 !! The second-last 1 gets pushed-out here too

F11 :  0 ->  F10 !! Still we have a second-last 1
F11 :  1 ->  F11 !! Stay in F11, as last two seen are 11

!!------------------------------------------------------------
''')
from math import floor, log, pow
def nthnumeric(N, Sigma={'a','b'}):
    """Assume Sigma is a 2-sized list/set of chars (default {'a','b'}). 
       Produce the Nth string in numeric order, where N >= 0.
       Idea : Given N, get b = floor(log_2(N+1)) - need that 
       many places; what to fill in the places is the binary 
       code for N - (2^b - 1) with 0 as Sigma[0] and 1 as Sigma[1].    
    """
    if (type(Sigma)==set):
       S = list(Sigma)
    else:
       assert(type(Sigma)==list
       ), "Expected to be given set/list for arg2 of nthnumeric."
       S = Sigma
    assert(len(Sigma)==2
          ),"Expected to be given a Sigma of length 2."
    if(N==0):
        return ''
    else:
        width = floor(log(N+1, 2))
        tofill = int(N - pow(2, width) + 1)
        relevant_binstr = bin(tofill)[2::] # strip the 0b 
                                           # in the leading string
        len_to_makeup = width - len(relevant_binstr)
        return (S[0]*len_to_makeup + 
                shomo(relevant_binstr,
                      lambda x: S[1] if x=='1' else S[0]))
nthnumeric(20,['0','1'])
run_dfa(secondLastIs1, '0101')
accepts_dfa(secondLastIs1, '0101')
tests = [ nthnumeric(i, ['0','1']) for i in range(12) ]
for t in tests:
    if accepts_dfa(secondLastIs1, t):
        print("This DFA accepts ", t)
    else:
        print("This DFA rejects ", t)
help(run_dfa)<jupyter_output>Help on function run_dfa in module jove.Def_DFA:

run_dfa(D, s)
    In : D (consistent DFA)
         s (string over D's sigma, including "")
    Out: next state of D["q0"] via string s<jupyter_text>This is an extensive illustration of union, intersection and complementation, DFA minimization, isomorphism test, language equivalence test, and an application of DeMorgan's law<jupyter_code>dfaOdd1s = md2mc('''
DFA
I : 0 -> I
I : 1 -> F
F : 0 -> F 
F : 1 -> I
''')
dotObj_dfa(dfaOdd1s)
dotObj_dfa(dfaOdd1s).source
ends0101 = md2mc('''
DFA 
I     : 0 -> S0  
I     : 1 -> I 
S0    : 0 -> S0 
S0    : 1 -> S01 
S01   : 0 -> S010 
S01   : 1 -> I 
S010  : 0 -> S0 
S010  : 1 -> F0101 
F0101 : 0 -> S010 
F0101 : 1 -> I 
''')
dotObj_dfa(ends0101)
dotObj_dfa(ends0101).source
odd1sORends0101 = union_dfa(dfaOdd1s,ends0101)
dotObj_dfa(odd1sORends0101)
dotObj_dfa(odd1sORends0101)
dotObj_dfa(odd1sORends0101).source
Minodd1sORends0101 = min_dfa(odd1sORends0101)
dotObj_dfa(Minodd1sORends0101)
dotObj_dfa(Minodd1sORends0101).source
iso_dfa(odd1sORends0101, Minodd1sORends0101)
langeq_dfa(odd1sORends0101, Minodd1sORends0101)
odd1sANDends0101 = intersect_dfa(dfaOdd1s,ends0101)
dotObj_dfa(odd1sANDends0101)
Minodd1sANDends0101 = min_dfa(odd1sANDends0101)
dotObj_dfa(Minodd1sANDends0101)
dotObj_dfa(Minodd1sANDends0101).source
CdfaOdd1s = comp_dfa(dfaOdd1s)
Cends0101 = comp_dfa(ends0101)
C_CdfaOdd1sORCends0101 = comp_dfa(union_dfa(CdfaOdd1s, Cends0101))
dotObj_dfa(C_CdfaOdd1sORCends0101)
MinC_CdfaOdd1sORCends0101 = min_dfa(C_CdfaOdd1sORCends0101)
dotObj_dfa(MinC_CdfaOdd1sORCends0101)
iso_dfa(MinC_CdfaOdd1sORCends0101, Minodd1sANDends0101)
blimp = md2mc('''
DFA 
I1 : a -> F2
I1 : b -> F3
F2 : a -> S8
F2 : b -> S5
F3 : a -> S7
F3 : b -> S4
S4 : a | b -> F6
S5 : a | b -> F6
F6 : a | b -> F6
S7 : a | b -> F6
S8 : a -> F6
S8 : b -> F9
F9 : a -> F9
F9 : b -> F6
''')
dblimp = dotObj_dfa(blimp)
dblimp
dblimp = dotObj_dfa(blimp, FuseEdges=True)
dblimp
dblimp.source
mblimp = min_dfa(blimp)
dmblimp = dotObj_dfa(mblimp)
dmblimp<jupyter_output><empty_output><jupyter_text>This shows how DeMorgan's Law applies to DFAs. It also shows how, using the tools provided to us, we can continually check our work.<jupyter_code>testdfa = md2mc('''DFA
I : 0 -> I
I : 1 -> F
F : 0 -> I
''')
testdfa
tot_testdfa = totalize_dfa(testdfa)
dotObj_dfa(tot_testdfa)
dotObj_dfa_w_bh
dotObj_dfa_w_bh(tot_testdfa)
dotObj_dfa_w_bh(tot_testdfa, FuseEdges = True)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.16160597195601736, 'fraction_numerical': 0.056642792292948656, 'mean_word_length': 2.2375898105813192, 'pattern_counts': {'":': 0, '<': 32, '<?xml version=': 0, '>': 108, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 25, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '8', 'dir': 'jupyter-structured-clean-dedup', 'id': '195090', 'license': 'Unlicense', 'n_tokens_mistral': 7857, 'n_tokens_neox': 7225, 'n_words': 2124, 'path': 'asgjove/asg1/Drive_DFA.ipynb', 'repo_name': 'em23/3100jove', 'size': '19826'}