code Python pour accepter la grammaire prédéfinie

Question

Je suis en train de faire un code pour reconnaître une chaîne de caractères qui suivent les règles de grammaire:

• S> ABK
• K-> x | xK | H
• H-> c | d

Alors que les mots comme ABX, abxxx, abc, abxd, abxc, etc ... sont acceptées et des mots comme ab, abb, xxx, etc ... ne sont pas acceptés.

J'ai écrit un code pour faire ça et dans mon analyse ça devrait faire l'affaire, mais il y a quelque chose qui ne va pas, ça renvoie False pour abxx, une phrase qui devrait être acceptée par la grammaire et je pense a à voir avec les valeurs de retour imbriquées des fonctions, que je ne comprends pas très bien.

Le code sera collé ci-dessous, si vous les gars pouvez comprendre ou me signaler ce que je fais mal, je serai reconnaissant.

def S(word): 
    if word[0] == 'a': 
     atual = 1 
    else: 
     return False 
    if word[1] == 'b': 
     atual = 2 
    else: 
     return False 
    accepted = K(atual, word) 
    if accepted == True: 
     return True 
    else: 
     return False 

def K(atual, word): 
    if word[atual] == 'x': 
     atual += 1 
     if len(word) <= atual: # checks to see if the word ended and accept by the first rule of the set K. 
      return True 
     else: 
      K(atual, word) # keeps increasing the value of atual, satisfying the rule xK 
    else: 
     value = H(atual, word) # if no more 'x' are found, try the rule H 
     return value 

def H(atual, word): 
    if word[atual] == 'c' or word[atual] == 'd': 
     return True 
    else: 
     return False 

print(S(['a','b','x','x'])) 

Answer 1

Votre mise en œuvre est inutilement bavard et répétitif: il n'y a pas besoin de passer autour de l'index, par exemple, quand vous pouvez passer à la fonction suivante la partie pertinente du mot. Voici une mise en œuvre rapide, je lançai ensemble qui devrait le résoudre:

def S(chars): 
    word = ''.join(chars) 
    try: 
    return word[:2] == 'ab' and K(word[2:]) 
    except IndexError: 
    return False 

def K(word): 
    return word == 'x' or (word[0] == 'x' and K(word[1:])) or H(word) 

def H(word): 
    return word in ['c', 'd'] 

Cette fonction, je reçois:

>>> list(map(S, ['abx', 'abxxx', 'abc', 'abxd', 'abxc'])) 
[True, True, True, True, True]