Python code to accept pre-defined grammar
<p>I'm trying to make a code to recognize a chain of characters following the grammar rules:</p>

<ul>
<li>S-> abK</li>
<li>K-> x|xK|H</li>
<li>H-> c|d</li>
</ul>

<p>So that words like <em>abx</em>, <em>abxxx</em>, <em>abc</em>, <em>abxd</em>, <em>abxc</em>, etc... are all accepted and words like <em>ab</em>, <em>abb</em>, <em>xxx</em>, etc... aren't accepted.</p>

<p>I wrote a code to do that and in my analysis it should do the trick, but there is something wrong in it, i.e, it returns False for abxx, a sentence that should be accepted by the grammar and I think it has to do with nested return values from functions, which I don't understand very well. </p>

<p>The code will be pasted below, if you guys can figure out or point me what I'm doing wrong I will be thankful.</p>

<pre><code>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) &lt;= 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']))
</code></pre>

<p>Your implementation is unnecessarily verbose and repetitive: there is no need to pass around the index, for instance, when you can just pass to the next function the relevant part of the word. Here is a quick implementation I threw together that should resolve it:</p>

<pre><code>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']
</code></pre>

<p>Using this function, I get:</p>

<pre><code>&gt;&gt;&gt; list(map(S, ['abx', 'abxxx', 'abc', 'abxd', 'abxc']))
[True, True, True, True, True]
</code></pre>

python grammar