Below are examples of Python functions that act as recognizers or deciders. For each of the functions,

$$ What is the language the function recognizes? Use set$-$builder notation if appropriate.

$$ Is the function a decider or just a recognizer? Why?

For this exercise, let $\backslash$Sigma $=\{$a$,$b$\},$ meaning that you only need to consider input strings made of as and bs$.$

a$.$ Answer the questions above about this function:

def arthur$($w: str$)->$ bool:

length $=$ len$($w$)$

if length $\%2==1$:

return False

# Indices within strings range from $0($the first

# character$)$ to length $-1($the last character$).$

for i in range$(0,$ length $/2)$:

if $($w$[$i$]!="$a$")$ or $($w$[$length $-1-$ i$]!="$b$")$:

return False

return True

b$.$ Answer the questions above about this function:

def zaphod$($w: str$)->$ bool:

strings $=[""]$

while True:

next$\_$strings $=[]$

for x in strings:

if w $==$ x:

return True

next$\_$strings.append$($x $+"$a$")$

next$\_$strings.append$($x $+"$b$")$

# On the next iteration through the $$while$$ loop,

# use next$\_$strings for the $$for$$ loop.

strings $=$ next$\_$strings

c$.$ Answer the questions above about this function:

def trillian$($w: str$)->$ bool:

x $=0$

y $=1$

while len$($w$)!=$ x:

z $=$ x $+$ y

x $=$ y

y $=$ z

return True