Modify the rewriting system search Jupyter NB program.

so that

a$.$ it implements $($limited depth$)$ DFS$.$

b$.$ It must take a text file in the following format as input. The contains as separate lines:

i$.$ Initial state

ii$.$ Goal states $($possibly more than one separated by space$)$

iii. Rewriting rules of the system. Each rule is in the format $$premise$,$ consequent$.$

Two rules are separated by space.

iv$.$ Maximum depth

Example of a file contents is given below:

E

abbba babba

E$,$a a$,$ab a$,$ba b$,$bba b$,$bbba

$10$

c$.$ The following modifications should be made:

$$ The data structure for the goal should now be either a set or a list,

$$ The termination condition in the search routine should be changed to a membership

in goal set $($list$),$

$$ Input file must be parsed so that the rules dictionary for the call to search function

can be created from the file.

For help with string processing and with file input see in the Intro to Python Jupyter NBs folder

wait i will give you the code that is mentioned above so that you can modify as per the task.

import collections

class Rewriting$\_$system:

def $\_\_$init$\_\_($self$)$:

self.productions $=\{\}$

def lhs$($self$)$:

return self.productions.keys$()$

def rhs$($self$,$ id$)$:

return self.productions$[$id$]$

class BFSFrontier:

def $\_\_$init$\_\_($self$)$:

self.elements $=$ collections.deque$()$

def empty$($self$)$:

return len$($self$.$elements$)==0$

def put$($self$,$ x$)$:

self.elements.append$($x$)$

def get$($self$)$:

return self.elements.popleft$()$

def occurences$($sub$,$ string$)$:

positions$=[]$

count$=0$

for i in range$($len$($string$)-$len$($sub$)+1,-1,-1)$:

if $($sub in string$[$i:i$+$len$($sub$)])$:

# print$(\text{'}$found$\text{'},\text{'}$ in position',i$)$

positions$=$positions$+[$i$]$

return positions

def breadth$\_$first$\_$search$($system$,$ start, goal$)$:

if $($start$==$goal$)$:

return True

else:

count$=0$

frontier $=$ BFSFrontier$()$

frontier.put$($start$)$

visited $=\{\}$

visited$[$start$]=$ True

while not frontier.empty$()$:

count$=$count$+1$

print$($count$)$

current $=$ frontier.get$()$

print$("$Visiting $\%$r$"\%$ current$)$

for symbol in system.lhs$()$:

# print$($symbol$)$

# print$(\text{'}$occurs$\text{'},$len$($occurences$($symbol$,$current$)),\text{'}$ times'$)$

if $($len$($occurences$($symbol$,$current$))!=0)$:

replace$\_$positions$=$occurences$($symbol$,$current$)$

print$($replace$\_$positions$)$

print$($system$.$rhs$($symbol$))$

for s in system.rhs$($symbol$)$:

#print$(\text{'}$replacement$\text{'},$ s$)$

for i in replace$\_$positions:

next$=$current$[0$:i$]+$s$+$current$[$i$+$len$($symbol$)$:$]$

#print$(\text{'}$next generated state is$\text{'},$next$)$

if $($next$==$goal$)$:

return True

else:

if next not in visited:

print$(\text{'}$new state in frontier is$\text{'},$ next$)$

frontier.put$($next$)$

visited$[$next$]=$ True

example$\_$system$=$Rewriting$\_$system$()$

example$\_$system.productions $=\{$

$\text{'}$E$\text{'}$:$[\text{'}$a$\text{'}],$

$\text{'}$a$\text{'}$: $[\text{'}$ab$\text{'},\text{'}$ba$\text{'}],$

$\text{'}$b$\text{'}$:$[\text{'}$bbb$\text{'},$'bba'$]\}$

empty$\_$word$=\text{'}$E$\text{'}$

goal$=$'babbba'

breadth$\_$first$\_$search$($example$\_$system,empty$\_$word,goal$)$

Note: dont do it with depth limited search and dont use max depth also just do it with simple BFS $($breadth first search$)$