<jupyter_start><jupyter_text>RE operationsYou may watch a portion of the following Youtube video (fast-forwarding as needed) to obtainan overview of RE-related operations.We will discuss:* REs for some simple languages* RE to NFA conversion* NFA to RE conversion<jupyter_code># This Youtube video walks through many RE operations
from IPython.display import YouTubeVideo
YouTubeVideo('eXjIYsalFEQ')

import sys
sys.path[0:0] = ['../..','../../3rdparty'] # Put these at the head of the search path

from jove.DotBashers import *
from jove.Def_DFA import *
from jove.Def_NFA import *
from jove.Def_RE2NFA import *
from jove.Def_NFA2RE import *
from jove.Def_md2mc import *<jupyter_output>You may use any of these help commands:
help(ResetStNum)
help(NxtStateStr)

You may use any of these help commands:
help(mkp_dfa)
help(mk_dfa)
help(totalize_dfa)
help(addtosigma_delta)
help(step_dfa)
help(run_dfa)
help(accepts_dfa)
help(comp_dfa)
help(union_dfa)
help(intersect_dfa)
help(pruneUnreach)
help(iso_dfa)
help(langeq_dfa)
help(same_status)
help(h_langeq_dfa)
help(fixptDist)
help(min_dfa)
help(pairFR)
help(state_combos)
help(sepFinNonFin)
help(bash_eql_classes)
help(listminus)
help(bash_1)
help(mk_rep_eqc)
help(F_of)
help(rep_of_s)
help(q0_of)
help(Delta_of)
help(mk_state_eqc_name)

You may use any of these help commands:
help(mk_nfa)
help(totalize_nfa)
help(step_nfa)
help(run_nfa)
help(ec_step_nfa)
help(Eclosure)
help(Echelp)
help(accepts_nfa)
help(nfa2dfa)
help(n2d)
help(inSets)
help(rev_dfa)
help(min_dfa_brz)

You may use any of these help commands:
help(re2nfa)

You may use any of these help commands:
help(RE2Str)
help(mk_gnfa)
help(mk_gnfa_from_D)
help(dfa2nfa)
help(del_gn[...]<jupyter_text>We will develop REs for some example languages<jupyter_code># RE for the language of odd 1's (over the alphabet {0,1})

RE_Odd1s  = "(0* 1 0* (1 0* 1 0*)*)"
NFA_Odd1s = re2nfa(RE_Odd1s)
DO_Odd1s  = dotObj_dfa(min_dfa(nfa2dfa(NFA_Odd1s)))
DO_Odd1s
# RE for the language of exactly three 0's 

RE_Ex3z = "1* 0 1* 0 1* 0 1*"
NFA_Ex3z = re2nfa(RE_Ex3z)
DO_Ex3z  = dotObj_dfa(min_dfa(nfa2dfa(NFA_Ex3z)))
DO_Ex3z
# RE for odd 1's or exactly three 0's

RE_O13z  = "0* 1 0* (1 0* 1 0*)* + 1* 0 1* 0 1* 0 1* "
NFA_O13z = re2nfa(RE_O13z)
MD_O13z  = min_dfa(nfa2dfa(NFA_O13z))
DO_O13z  = dotObj_dfa(MD_O13z)
DO_O13z<jupyter_output>Generating LALR tables<jupyter_text>Examples of RE to NFA conversion<jupyter_code>dotObj_dfa(min_dfa(nfa2dfa(re2nfa("''"))))
# DFA for the language of "aa" generated via re2nfa, nfa2dfa and min_dfa

D1 = min_dfa(nfa2dfa(re2nfa("aa")))
dotObj_dfa(D1)
# DFA for the language of "bb" generated via re2nfa, nfa2dfa and min_dfa

D2 = min_dfa(nfa2dfa(re2nfa("bb")))
dotObj_dfa(D2)
D1
D2
# The union of the DFA of the aforesaid languages, i.e. {aa,bb}

D1or2 = min_dfa(union_dfa(D1,D2))
D1or2p = pruneUnreach(D1or2)
dotObj_dfa(D1or2)
# The intersection of {aa} and {bb}

D1and2 = min_dfa(intersect_dfa(D1,D2))
D1and2p = pruneUnreach(D1and2)
dotObj_dfa(D1and2)
dotObj_dfa_w_bh(D1and2p, FuseEdges=True)
# Another example of the power of the conversions and checking facilities for DFA equivalence


d1=nfa2dfa(re2nfa("abcde"))
d2=nfa2dfa(re2nfa("abced"))
langeq_dfa(d1,d2,True)<jupyter_output>The DFA are NOT language equivalent!
Path leading to counterexample is: 
[("{'St1'}", "{'St1'}"), ("{'St2', 'St3'}", "{'St2', 'St3'}"), ("{'St4', 'St5'}", "{'St4', 'St5'}"), ("{'St6', 'St7'}", "{'St6', 'St7'}"), ("{'St8', 'St9'}", 'BH'), ("{'St10'}", 'BH')]<jupyter_text>CounterexamplesWhen two DFA are not equivalent, one can obtain a counterexample heping us debug. The counterexampleis a sequence of pairs of DFA states.```Here the path is("{'St1'}", "{'St1'}"),                  -- this pair of states exists in the DFAs below("{'St2', 'St3'}", "{'St2', 'St3'}"),    -- this pair also exists("{'St4', 'St5'}", "{'St4', 'St5'}"),    -- so does this("{'St6', 'St7'}", "{'St6', 'St7'}"),    -- so does this  ('BH', "{'St8', 'St9'}"),                -- oops, one machine goes into the BH, the other not('BH', "{'St10'}")                       -- this too; one machine goes to St10, the other is BH```<jupyter_code>dotObj_dfa(d1)
dotObj_dfa(d2)
# Two other RE-based languages that are not equivalent
# We can read the counterexample the same way

d1a=nfa2dfa(re2nfa("aa*+bc"))
d2a=nfa2dfa(re2nfa("a(a*+bc)"))
langeq_dfa(d1a,d2a,True)
dotObj_dfa(d1a)
dotObj_dfa(d2a)
d1b=nfa2dfa(re2nfa("aaa*+aa*bc+bcaa*+bcbc"))
d2b=nfa2dfa(re2nfa("(aa*+bc)(aa*+bc)"))
langeq_dfa(d1b,d2b,True)
dotObj_dfa(d1b)
dotObj_dfa(d2b)
iso_dfa(d1b,d2b)
d1c=min_dfa(d1b)
d2c=min_dfa(d2b)
iso_dfa(d1c,d2c)
dotObj_dfa(d1c)
dotObj_dfa(d2c)
d1d=nfa2dfa(re2nfa("aaa*+aa*bc+bcaaa*+bcbc"))
d2d=nfa2dfa(re2nfa("(aa*+bc)(aa*+bc)"))
langeq_dfa(d1d,d2d,True)
d1d=nfa2dfa(re2nfa("a a a*+a a* b c+ b c a a a*+b c b c"))
d2d=nfa2dfa(re2nfa("(a a*+b c)(a a*+b c)"))
langeq_dfa(d1d,d2d,True)
dotObj_dfa(d1d)
dotObj_dfa(d2d)
d1d=nfa2dfa(re2nfa("james*+bond*"))
dotObj_dfa(d1d)
d1d=nfa2dfa(re2nfa("ja mes*+bo nd*"))
dotObj_dfa(d1d)
d1d=nfa2dfa(re2nfa("''"))
dotObj_dfa(d1d)
test = md2mc(src="File", fname="endsin0101.nfa")
dotObj_nfa(test)
# NFA for 0101 within hamming dist of 2
nfamd1 = md2mc(src="File", fname="nfa0101h2.nfa")
dotObj_nfa(nfamd1)
dfamd1=nfa2dfa(nfamd1)
dotObj_dfa(dfamd1)
m1=min_dfa(dfamd1)
m2=min_dfa_brz(dfamd1)
dotObj_dfa(m1)
dotObj_dfa(m2)
iso_dfa(m1,m2)<jupyter_output><empty_output><jupyter_text>We will now illustrate NFA to RE conversionThe workhorse function is del_gnfa_states<jupyter_code>help(del_gnfa_states)
gnfamd1=mk_gnfa(nfamd1)
dotObj_gnfa(gnfamd1)
(Gfinal, dotObj_List, final_re_str) = del_gnfa_states(gnfamd1)
final_re_str
dotObj_List[0]
dotObj_List[1]
dotObj_List[2]
dotObj_List[3]
dotObj_List[4]
len(dotObj_List)
dotObj_List[11]
final_re_str<jupyter_output><empty_output><jupyter_text>Let us go full circle!The obtained final RE string is fed back into the conversion pipeline<jupyter_code>fullcircle=min_dfa(nfa2dfa(re2nfa(final_re_str)))
dotObj_dfa(fullcircle)
# This is the two-bit hamming distance machine wrt the intended pattern 0101

h2_from_re = min_dfa(nfa2dfa(re2nfa("(0+1)(0+1)01 + (0+1)1(0+1)1 + (0+1)10(0+1) + 0(0+1)(0+1)1 + 0(0+1)0(0+1) + 01(0+1)(0+1)")))
dotObj_dfa(h2_from_re)
iso_dfa(fullcircle,h2_from_re)
epsre
are
aplusbre
abre
arestar
aplusbstar
aplusb_aplusbstar
aplusb_aplusb = dotObj_nfa(re2nfa("(a+b)(a+b)"), True)
aplusb_aplusb
DOodd1s_or_30s = dotObj_nfa(re2nfa("0* 1 0* (1 0* 1 0*)* + 1* 0 1* 0 1* 0 1* "), True)
DOodd1s_or_30s
DOodd1s_or_30s = dotObj_nfa(re2nfa("0* 1 0* (1 0* 1 0*)* + 1* 0 1* 0 1* 0 1* "), False)
DOodd1s_or_30s
DOodd1s_or_30s_mind = dotObj_dfa(min_dfa(nfa2dfa(re2nfa("0* 1 0* (1 0* 1 0*)* + 1* 0 1* 0 1* 0 1* "))))
DOodd1s_or_30s_mind<jupyter_output><empty_output><jupyter_text>Designing DFA that accept within a Hamming Distance Given a regular language, say (0+1)* 0101 (0+1)* (i.e., all bit-strings with an occurrence of 0101 in it), let us come up with 1. An RE that represents strings within a Hamming distance of 2 from strings in this language2. An NFA that represents strings within a Hamming distance of 2 from strings in this language<jupyter_code>h2_0101_re = ("(0+1)* ( (0+1)(0+1)01 +" + 
                      " (0+1)1(0+1)1 +" + 
                      " (0+1)10(0+1) +" + 
                      " 0(0+1)(0+1)1 +" +
                      " 0(0+1)0(0+1) +" +
                      " 01(0+1)(0+1) )" +
              "(0+1)*")
h2_0101_re
minD_h2_0101_re = min_dfa(nfa2dfa(re2nfa(h2_0101_re)))
DO_minD_h2_0101_re = dotObj_dfa(minD_h2_0101_re)
DO_minD_h2_0101_re
DO_minD_h2_0101_re.source
h2_0101_nfa_md = '''
NFA
!!--------------------------------------------
!! We are supposed to process (0+1)*0101(0+1)*
!! with up to two "dings" allowed
!!
!! Approach: Silently error-correct, but remember
!! each "ding" in a new state name.
!! After two dings, do not error-correct anymore
!!--------------------------------------------

!!-- pattern for (0+1)* is the usual
!!-- no error-correction needed here :-)
I : 0 | 1 -> I

!!-- Now comes the opportunity to exit I via 0101
!!-- The state names are A,B,C,D with ding-count
!!-- Thus A0 is A with 0 dings
!!-- C2 is C with 2 dings; etc

!!-- Ding-less traversal -- how lucky!
I  : 0 -> A0
A0 : 1 -> B0
B0 : 0 -> C0
C0 : 1 -> F
!!-- Phew, finally at F
F  : 0 | 1 -> F

!!-- First ding in any of these cases
I  : 1 -> A1
A0 : 0 -> B1
B0 : 1 -> C1
C0 : 0 -> F  !!-- ding-recording un-nec.; just goto F

!!-- Second ding in any of these cases
A1 : 0 -> B2
B1 : 1 -> C2
C1 : 0 -> F  !!-- ding-recording un-nec.; just goto F

!!-- No more dings allowed!
B2 : 0 -> C2
C2 : 1 -> F

!!-- Allow one-dingers to finish fine
A1 : 1 -> B1
B1 : 0 -> C1
C1 : 1 -> F

'''
h2_0101_nfa = md2mc(h2_0101_nfa_md)
DO_h2_0101_nfa = dotObj_nfa(h2_0101_nfa)
DO_h2_0101_nfa
minD_h2_0101_nfa = min_dfa(nfa2dfa(h2_0101_nfa))
DO_minD_h2_0101_nfa = dotObj_dfa(minD_h2_0101_nfa)
DO_minD_h2_0101_nfa
iso_dfa(minD_h2_0101_re, minD_h2_0101_nfa)
nfaEx = md2mc('''NFA
I : '' -> B
I : a  -> A
!!A : b  -> I
A : q  -> F
A : r  -> B
B : s  -> B
B : p  -> F
F : t  -> A
''')
DO_nfaEx = dotObj_nfa(nfaEx)
DO_nfaEx
GNFA_nfaEx = mk_gnfa(nfaEx)
help(del_gnfa_states)
(Gfinal, do_list, final_re) = del_gnfa_states(GNFA_nfaEx)
final_re
final_re
do_list[0]
do_list[1]
do_list[1]
do_list[2]
do_list[2].source
do_list[3]
do_list[3].source
do_list[4]
do_list[4].source
re_mindfa = min_dfa(nfa2dfa(re2nfa(final_re)))
dir_mindfa = min_dfa(nfa2dfa(nfaEx))
iso_dfa(re_mindfa,dir_mindfa)
dotObj_dfa(dir_mindfa)
dotObj_dfa(re_mindfa)
dot_san_str('""')
nfaExp = md2mc('''NFA
I : a -> A1
I : n -> B1
A1 : b -> AB1
B1 : o -> AB1
AB1 : c -> A2
AB1 : p -> B2
A2 : d -> AB2
B2 : q -> AB2
AB2 : e -> A3
AB2 : r -> B3
A3 : f -> AB3
B3 : s -> AB3
AB3 : g -> A4
AB3 : t -> B4
A4 : h -> FAB4
B4 : u -> FAB4
''')
DO_nfaExp = dotObj_nfa(nfaExp)
DO_nfaExp
gnfaExp = mk_gnfa(nfaExp)
DO_gnfaExp = dotObj_gnfa(gnfaExp)
DO_gnfaExp
(Gfinal, dotObj_List, final_re_str) = del_gnfa_states(gnfaExp)
final_re_str
nfaExer = md2mc('''NFA
I1 : a -> X
I2 : b -> X
I3 : c -> X
X  : p | q -> X
X  : m -> F1
X  : n -> F2
''')
DO_nfaExer = dotObj_nfa(nfaExer)
DO_nfaExer
gnfaExer = mk_gnfa(nfaExer)
DO_gnfaExer = dotObj_gnfa(gnfaExer)
DO_gnfaExer
(G, DO, RE) = del_gnfa_states(gnfaExer)
RE
DO_nfaExer
DO[0]
DO[1]
DO[2]
DO[3]
DO[4]
DO[5]
DO[6]
nfaExer = md2mc('''NFA
I1 : a -> X
I2 : b -> X
I3 : c -> X
X  : p | q -> X
X  : m -> F1
X  : n -> F2
''')
DO_nfaExer = dotObj_nfa(nfaExer)
DO_nfaExer
gnfaExer = mk_gnfa(nfaExer)
DO_gnfaExer = dotObj_gnfa(gnfaExer)
DO_gnfaExer
(G, DO, RE) = del_gnfa_states(gnfaExer, DelList=["X", "I1", "I2","I3","F1","F2"])
DO_gnfaExer
len(DO)
RE
DO[0]
DO[1]
DO[2]
DO[3]
DO[4]
DO[5]
DO[6]
RE
sylv_11_13 = min_dfa(nfa2dfa(re2nfa("(11111111111+1111111111111)*")))
dotObj_dfa(sylv_11_13)
sylv_11_13
sylv_3_5 = min_dfa(nfa2dfa(re2nfa("(111+11111)*")))
len(sylv_3_5["Q"]) - 2
3*5-3-5
dotObj_dfa(sylv_3_5)
dotObj_nfa(re2nfa("(111+11111)*"))
nfa_3_5 = re2nfa("(111+11111)*")
nfa_3_5
dotObj_nfa(nfa_3_5)
Gnfa_3_5 = mk_gnfa(nfa_3_5)
Gnfa_3_5
dotObj_gnfa(Gnfa_3_5)
(Gfinal, dotObj_List, final_re_str) = del_gnfa_states(Gnfa_3_5)
len(dotObj_List)
dotObj_List[0]
dotObj_List[1]
dotObj_List[2]
dotObj_List[3]
dotObj_List[4]
dotObj_List[5]
dotObj_List[6]
dotObj_List[7]
dotObj_List[8]
dotObj_List[9]
dotObj_List[10]
dotObj_List[11]
dotObj_List[12]
dotObj_List[13]
dotObj_List[14]
dotObj_List[15]
dotObj_List[16]
dotObj_List[17]
len(dotObj_List)
final_re_str
dotObj_gnfa(mk_gnfa(re2nfa("(111+11111)*")))
minD_renfare = min_dfa(nfa2dfa(re2nfa(final_re_str)))
DOminD_renfare = dotObj_dfa(minD_renfare)
DOminD_renfare
dotObj_dfa(min_dfa(nfa2dfa(nfa_3_5)))
dotObj_dfa(min_dfa(nfa2dfa(re2nfa("(111+11111)*"))))
sylv_3_5 = min_dfa(nfa2dfa(re2nfa("(111+11111)*")))
len(sylv_3_5["Q"]) - 1 - 1
DO_sylv_3_5 = dotObj_dfa(sylv_3_5)
non_sylv_3_6 = min_dfa(nfa2dfa(re2nfa("(111+111111)*")))
DO_non_sylv_3_6 = dotObj_dfa(non_sylv_3_6)
DO_non_sylv_3_6
non_sylv_prefix_and_3_6 = min_dfa(nfa2dfa(re2nfa("111(111+111111)*")))
DO_non = dotObj_dfa(non_sylv_prefix_and_3_6)
DO_non
stamp_3_5_7 = min_dfa(nfa2dfa(re2nfa("(111+11111+1111111)*")))
DOstamp_3_5_7 = dotObj_dfa(stamp_3_5_7)
DOstamp_3_5_7
len(min_dfa(nfa2dfa(re2nfa("(111+1111111111111)*")))["Q"]) - 2
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
nfaBESame = apply_h_dfa(dfaBESame, lambda x: '0')
nfaBESame
DONFABESame = dotObj_nfa(nfaBESame)
DONFABESame
dotObj_dfa(nfa2dfa(nfaBESame))
dotObj_dfa(min_dfa(nfa2dfa(nfaBESame)))
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
''')
blimpnfa = apply_h_dfa(blimp, lambda x: 'a')
dotObj_nfa(blimpnfa)
dotObj_dfa(nfa2dfa(blimpnfa))
dotObj_dfa(min_dfa(nfa2dfa(blimpnfa)))
testdfa = md2mc('''DFA
I : 0 | 1 -> I
I : 2 -> F
''')
dotObj_dfa_w_bh(testdfa)
help(dotObj_dfa_w_bh)
dotObj_dfa(testdfa, FuseEdges=True)
dotObj_dfa(min_dfa(nfa2dfa(re2nfa("(111+11111)*"))))
dotObj_dfa(min_dfa(nfa2dfa(re2nfa("(111+1111111111111)*"))))
ResetStNum()
dotObj_dfa(min_dfa(nfa2dfa(re2nfa("(111+1111111111111)*"))))
ResetStNum()
dotObj_dfa(min_dfa(nfa2dfa(re2nfa("(111+1111111111111)*"))))<jupyter_output>Generating LALR tables
{'fraction_non_alphanumeric': 0.1647786555373379, 'fraction_numerical': 0.07974362796243852, 'mean_word_length': 5.121806569343065, 'pattern_counts': {'":': 0, '<': 25, '<?xml version=': 0, '>': 105, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 7, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '7', 'dir': 'jupyter-structured-clean-dedup', 'id': '601814', 'license': 'Unlicense', 'n_tokens_mistral': 7083, 'n_tokens_neox': 6657, 'n_words': 1331, 'path': 'First_Jove_Tutorial/CH8-9/CH8-9.ipynb', 'repo_name': 'Thanhson89/JA', 'size': '13418'}